{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Largest Rectangle in Histogram"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestRectangleArea"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #柱状图中最大的矩形"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定 <em>n</em> 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。</p>\n",
    "\n",
    "<p>求在该柱状图中，能够勾勒出来的矩形的最大面积。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>heights = [2,1,5,6,2,3]\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>最大的矩形为图中红色区域，面积为 10\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/01/04/histogram-1.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong> heights = [2,4]\n",
    "<b>输出：</b> 4</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= heights.length <=10<sup>5</sup></code></li>\n",
    "\t<li><code>0 <= heights[i] <= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [largest-rectangle-in-histogram](https://leetcode.cn/problems/largest-rectangle-in-histogram/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [largest-rectangle-in-histogram](https://leetcode.cn/problems/largest-rectangle-in-histogram/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,5,6,2,3]', '[2,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "\n",
    "        stack = []\n",
    "        res = 0\n",
    "        i = 0\n",
    "        n = len(heights)\n",
    "        while i<n:\n",
    "            if not stack or heights[stack[-1]]<=heights[i]:\n",
    "                stack.append(i)\n",
    "                i += 1\n",
    "            else:\n",
    "                poped = stack.pop()\n",
    "                width = i if not stack else i-stack[-1]-1\n",
    "                res = max(res,width*heights[poped])\n",
    "        while stack:\n",
    "            poped = stack.pop()\n",
    "            width = len(heights) if not stack else i-stack[-1]-1\n",
    "            res = max(res,width*heights[poped])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = []\n",
    "        n = len(heights)\n",
    "        max_area = 0\n",
    "        for i in range(n):\n",
    "            while len(stack) > 0 and heights[stack[-1]] > heights[i]:\n",
    "                idx = stack.pop()\n",
    "                if len(stack) == 0:\n",
    "                    left_idx = -1\n",
    "                else:\n",
    "                    left_idx = stack[-1]\n",
    "                max_area = max(max_area, (i - left_idx - 1) * heights[idx])\n",
    "            stack.append(i)\n",
    "        \n",
    "        while len(stack) > 0:\n",
    "            idx = stack.pop()\n",
    "            if len(stack) == 0:\n",
    "                left_idx = -1\n",
    "            else:\n",
    "                left_idx = stack[-1]\n",
    "            max_area = max(max_area, (n - left_idx - 1) * heights[idx])\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        # 遍历每个元素，将其作为高，然后向左右扩展，记录面积进行比较.\n",
    "        def get_area(indexs,heights):\n",
    "            hi = heights[indexs]\n",
    "\n",
    "            left,right = indexs,indexs\n",
    "            while left>=1:\n",
    "                if heights[left-1]>=hi:\n",
    "                    left -= 1\n",
    "                else:\n",
    "                    break\n",
    "            while right<len(heights)-1:\n",
    "                if heights[right+1]>=hi:\n",
    "                    right += 1\n",
    "                else:\n",
    "                    break\n",
    "            area = (right-left+1)*hi\n",
    "            return area\n",
    "\n",
    "        cnt = 0\n",
    "        for i in range(len(heights)):\n",
    "            if i>0 and heights[i] == heights[i-1]: # 剪枝：相邻元素相等时可以跳过计算.\n",
    "                continue\n",
    "            cnt = max(cnt,get_area(i,heights))\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        max_area = 0\n",
    "        n = len(heights)\n",
    "        for i in range(n):\n",
    "            left = i - 1\n",
    "            right = i + 1\n",
    "            if n * heights[i] > max_area:\n",
    "                while left >= 0 and heights[left] >= heights[i]:\n",
    "                    left -= 1\n",
    "                while right <= n - 1 and heights[right] >= heights[i]:\n",
    "                    right += 1\n",
    "                max_area = max(max_area, (right - left - 1) * heights[i])\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stackh = [0]\n",
    "        stacki = [-1]\n",
    "        heights.append(0)\n",
    "        res = 0\n",
    "        for i in range(len(heights)):\n",
    "            if heights[i] > stackh[-1]:\n",
    "                stackh.append(heights[i])\n",
    "                stacki.append(i)\n",
    "            elif heights[i] == stackh[-1]:\n",
    "                stacki.pop()\n",
    "                stacki.append(i)\n",
    "            else:\n",
    "                while heights[i] < stackh[-1]:\n",
    "                    left = stacki[-2]\n",
    "                    right = i\n",
    "                    tmp = (right - left -1) * stackh.pop()\n",
    "                    res = max(res, tmp)\n",
    "                    stacki.pop()\n",
    "                if heights[i] > stackh[-1]:\n",
    "                    stacki.append(i)\n",
    "                    stackh.append(heights[i])\n",
    "                if heights[i] == stackh[-1]:\n",
    "                    stacki.pop()\n",
    "                    stacki.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        # 从小到大排序, [h, s, e]\n",
    "        l = []\n",
    "        ret = 0\n",
    "\n",
    "        for i, h in enumerate(heights):\n",
    "            p = bisect.bisect_left(l, [h])\n",
    "            if p == len(l):\n",
    "                l.append([h, i, i + 1])\n",
    "                continue\n",
    "\n",
    "            if l[p][0] == h:\n",
    "                l[p][2] = i + 1\n",
    "                if p + 1 == len(l):\n",
    "                    continue\n",
    "            else:\n",
    "                l.insert(p, [h, i, i + 1])\n",
    "\n",
    "            # 修改p的起始坐标\n",
    "            l[p][1] = min(l[p][1], l[p + 1][1])\n",
    "\n",
    "            # 计算后面面积及删除\n",
    "            e = l[-1][-1]\n",
    "            for i in range(p + 1, len(l)):\n",
    "                ret = max(ret, l[i][0] * (e - l[i][1]))\n",
    "\n",
    "            del l[p + 1:]\n",
    "\n",
    "        # 计算面积\n",
    "        e = l[-1][-1]\n",
    "        for i in range(len(l)):\n",
    "            ret = max(ret, l[i][0] * (e - l[i][1]))\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        ans = 0\n",
    "        heights.append(0)\n",
    "        heights.insert(0, 0)\n",
    "        stack = []\n",
    "        stack.append(0)\n",
    "\n",
    "        for i in range(1, len(heights)):\n",
    "            if heights[i] > heights[stack[-1]]:\n",
    "                stack.append(i)\n",
    "            elif heights[i] == heights[stack[-1]]:\n",
    "                stack.pop()\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                while len(stack) != 0 and heights[i] < heights[stack[-1]]:\n",
    "                    mid = stack.pop()\n",
    "                    if len(stack) != 0:\n",
    "                        left = stack[-1]\n",
    "                        right = i\n",
    "                        w = right - left - 1\n",
    "                        h = heights[mid]\n",
    "                        ans = max(ans, w * h)\n",
    "                stack.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack=[]\n",
    "        n=len(heights)\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            while len(stack) and heights[i]<heights[stack[-1]]:\n",
    "                index=stack.pop()\n",
    "                height=heights[index]\n",
    "                if len(stack)>0:\n",
    "                    width=i-stack[-1]-1\n",
    "                else:\n",
    "                    width=i\n",
    "                res=max(res, width*height)\n",
    "            stack.append(i)\n",
    "        while len(stack):\n",
    "            index=stack.pop()\n",
    "            height=heights[index]\n",
    "            if len(stack)>0:\n",
    "                width=n-stack[-1]-1\n",
    "            else:\n",
    "                width=n\n",
    "            res=max(res, width*height)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        stack = []        \n",
    "        left, right = [-1] * n, [n] * n\n",
    "        for i, x in enumerate(heights):\n",
    "            while stack and stack[-1][0] >= x:\n",
    "                right[stack[-1][1]] = i\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = stack[-1][1]\n",
    "            stack.append((x, i))\n",
    "        return max(heights[i] * (right[i] - left[i] - 1) for i in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        left, right = [0] * n, [n] * n\n",
    "\n",
    "        mono_stack = list()\n",
    "        for i in range(n):\n",
    "            while mono_stack and heights[mono_stack[-1]] >= heights[i]:\n",
    "                right[mono_stack[-1]] = i\n",
    "                mono_stack.pop()\n",
    "            left[i] = mono_stack[-1] if mono_stack else -1\n",
    "            mono_stack.append(i)\n",
    "        \n",
    "        ans = max((right[i] - left[i] - 1) * heights[i] for i in range(n)) if n > 0 else 0\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        left, right = [0] * n, [0] * n\n",
    "\n",
    "        mono_stack = list()\n",
    "        for i in range(n):\n",
    "            while mono_stack and heights[mono_stack[-1]] >= heights[i]:\n",
    "                mono_stack.pop()\n",
    "            left[i] = mono_stack[-1] if mono_stack else -1\n",
    "            mono_stack.append(i)\n",
    "        \n",
    "        mono_stack = list()\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while mono_stack and heights[mono_stack[-1]] >= heights[i]:\n",
    "                mono_stack.pop()\n",
    "            right[i] = mono_stack[-1] if mono_stack else n\n",
    "            mono_stack.append(i)\n",
    "        \n",
    "        ans = max((right[i] - left[i] - 1) * heights[i] for i in range(n)) if n > 0 else 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = []\n",
    "        maxn = 0\n",
    "        length = len(heights)\n",
    "        \n",
    "        heights.append(0)\n",
    "        heights.insert(0, 0)\n",
    "        #print(heights)\n",
    "        for idx in range(length+2):\n",
    "            while stack and (heights[idx] < heights[stack[-1]]):\n",
    "                sum = (idx - stack[-2] - 1)*heights[stack[-1]]\n",
    "                #print(idx, stack[-2], stack[-1], sum)\n",
    "                if sum > maxn:\n",
    "                    maxn = sum\n",
    "                print(maxn)\n",
    "                stack.pop()\n",
    "\n",
    "            stack.append(idx)\n",
    "            #print(heights[idx])\n",
    "\n",
    "        return maxn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        left, right = [0] * n, [0] * n\n",
    "\n",
    "        max_stack = []\n",
    "        for i in range(n):\n",
    "            while max_stack and heights[max_stack[-1]] >= heights[i]:\n",
    "                max_stack.pop()\n",
    "            if max_stack:\n",
    "                left[i] = max_stack[-1]\n",
    "            else:\n",
    "                left[i] = -1\n",
    "            max_stack.append(i)\n",
    "        max_stack.clear()\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while max_stack and heights[max_stack[-1]] >= heights[i]:\n",
    "                max_stack.pop()\n",
    "            if max_stack:\n",
    "                right[i] = max_stack[-1]\n",
    "            else:\n",
    "                right[i] = n\n",
    "            max_stack.append(i)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, (right[i] - left[i] - 1) * heights[i])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        left, right =[0] * n, [0] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while len(stack) > 0 and heights[i] <= heights[stack[-1]]:\n",
    "                stack.pop(-1)\n",
    "            left[i] = -1 if len(stack) == 0 else stack[-1]\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while len(stack) > 0 and heights[i] <= heights[stack[-1]]:\n",
    "                stack.pop(-1)\n",
    "            right[i] = n if len(stack) == 0 else stack[-1]\n",
    "            stack.append(i)\n",
    "        area = 0\n",
    "        for i in range(n):\n",
    "            area = max(area, heights[i] * (right[i] - left[i] -  1))\n",
    "        return area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        left, right = [0] * n, [n] * n\n",
    "\n",
    "        max_stack = []\n",
    "        for i in range(n):\n",
    "            while max_stack and heights[max_stack[-1]] >= heights[i]:\n",
    "                right[max_stack[-1]] = i \n",
    "                max_stack.pop()\n",
    "            if max_stack:\n",
    "                left[i] = max_stack[-1]\n",
    "            else:\n",
    "                left[i] = -1\n",
    "            max_stack.append(i)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, (right[i] - left[i] - 1) * heights[i]) \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        heights.append(0)\n",
    "        n = len(heights)\n",
    "        arr = [-1,0]\n",
    "        res = 0\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if heights[arr[-1]] < heights[i]:\n",
    "                arr.append(i)\n",
    "            else:\n",
    "                while heights[arr[-1]] > heights[i]:\n",
    "                    t = arr.pop()\n",
    "                    res = max(res, heights[t]*(i-arr[-1]-1))\n",
    "                arr.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        st = [-1]\n",
    "        ans = 0\n",
    "        heights.append(0)\n",
    "        for i, h in enumerate(heights):\n",
    "            while len(st) != 1 and heights[st[-1]] > h:\n",
    "                j = st.pop()  # 栈顶（下标）\n",
    "                hj = heights[j]  # 对顶的高度\n",
    "                left = st[-1]  # 刚刚出战的高度往左最远能到的位置\n",
    "                ans = max(ans, hj * (i - left - 1))\n",
    "            st.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = []\n",
    "        heights.append(0)\n",
    "        heights.insert(0, 0)\n",
    "        n, ans = len(heights), 0\n",
    "\n",
    "        for i in range(n):\n",
    "            while stack and heights[i] < heights[stack[-1]]:\n",
    "                mid = stack.pop()\n",
    "                if stack:\n",
    "                    left = stack[-1]\n",
    "                    right = i\n",
    "                    w = right - left - 1\n",
    "                    h = heights[mid]\n",
    "                    ans = max(ans, w * h)\n",
    "            stack.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = []\n",
    "        heights.append(0)\n",
    "        heights.insert(0, 0)\n",
    "        n, ans = len(heights), 0\n",
    "\n",
    "        for i in range(n):\n",
    "            while stack and heights[i] < heights[stack[-1]]:\n",
    "                mid = stack.pop()\n",
    "                if stack:\n",
    "                    right = i\n",
    "                    left = stack[-1]\n",
    "                    w = right - left - 1\n",
    "                    h = heights[mid]\n",
    "                    ans = max(ans, w * h)\n",
    "\n",
    "            stack.append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        left, right = [0] * n, [0] * n\n",
    "\n",
    "        mono_stack = []\n",
    "        for i in range(n):\n",
    "            while mono_stack and heights[mono_stack[-1]] >= heights[i]:\n",
    "                mono_stack.pop()\n",
    "            left[i] = mono_stack[-1] if mono_stack else -1\n",
    "            mono_stack.append(i)\n",
    "        mono_stack = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while mono_stack and heights[mono_stack[-1]] >= heights[i]:\n",
    "                mono_stack.pop()\n",
    "            right[i] = mono_stack[-1] if mono_stack else n\n",
    "            mono_stack.append(i)\n",
    "        ans = max((right[i] - left[i] - 1) * heights[i] for i in range(n))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        # 单调栈思想\n",
    "        if not heights:\n",
    "            return 0\n",
    "        n = len(heights)\n",
    "        if n==1:\n",
    "            return heights[0]\n",
    "        new_h = [-1 for i in range(n+2)]\n",
    "        for i in range(1,n+1):\n",
    "            new_h[i] = heights[i-1]\n",
    "        r = 0\n",
    "        stack = []\n",
    "        max_area = -float('inf')\n",
    "        while r <= n+1:\n",
    "            while stack and new_h[stack[-1]] > new_h[r]:\n",
    "                p = stack.pop()\n",
    "                l = -1 if not stack else stack[-1]\n",
    "                #l = stack.pop()\n",
    "                area = new_h[p] * (r-l-1)\n",
    "                if area > max_area:\n",
    "                    max_area = area\n",
    "            stack.append(r)\n",
    "            r+=1\n",
    "        return max_area\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        # 单调栈思想\n",
    "        if not heights:\n",
    "            return 0\n",
    "        n = len(heights)\n",
    "        if n==1:\n",
    "            return heights[0]\n",
    "        new_h = [-1 for i in range(n+2)]\n",
    "        for i in range(1,n+1):\n",
    "            new_h[i] = heights[i-1]\n",
    "        r = 0\n",
    "        stack = []\n",
    "        max_area = -float('inf')\n",
    "        while r <= n+1:\n",
    "            while stack and new_h[stack[-1]] > new_h[r]:\n",
    "                p = stack.pop()\n",
    "                l = -1 if not stack else stack[-1]\n",
    "                #l = stack.pop()\n",
    "                area = new_h[p] * (r-l-1)\n",
    "                if area > max_area:\n",
    "                    max_area = area\n",
    "            stack.append(r)\n",
    "            r+=1\n",
    "        return max_area\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        left = [-1]*n\n",
    "        right = [n]*n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and heights[stack[-1]] > heights[i]:\n",
    "                right[stack.pop()] = i\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, heights[i]*(right[i]-left[i]-1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        #两次循环找出左右边界即可\n",
    "        #以左侧边界为例，如果左侧值比当前值高，那么当前值的左侧边界就是左侧值的左侧边界，反之就是自己\n",
    "        #最左边的左侧边界只能是自己\n",
    "        #右侧则是一样\n",
    "        left = [-1]\n",
    "        stack = [0]\n",
    "        for i in range(1,len(heights)):\n",
    "            while stack and heights[i] <= heights[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                left.append(-1)\n",
    "            else:\n",
    "                left.append(stack[-1])\n",
    "            stack.append(i)\n",
    "        right = [len(heights)]\n",
    "        stack = [len(heights)-1]\n",
    "        for i in range(1,len(heights)):\n",
    "            i = len(heights)-1-i\n",
    "            while stack and heights[i] <= heights[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                right.append(len(heights))\n",
    "            else:\n",
    "                right.append(stack[-1])\n",
    "            stack.append(i)\n",
    "        right = right[::-1]\n",
    "        max1 = 0\n",
    "        for i in range(len(left)):\n",
    "            if (right[i] - left[i] - 1) * heights[i] > max1:\n",
    "                max1 = (right[i] - left[i] - 1) * heights[i]\n",
    "        return max1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        left, right =[0] * n, [0] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while len(stack) > 0 and heights[i] <= heights[stack[-1]]:\n",
    "                stack.pop(-1)\n",
    "            left[i] = -1 if len(stack) == 0 else stack[-1]\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while len(stack) > 0 and heights[i] <= heights[stack[-1]]:\n",
    "                stack.pop(-1)\n",
    "            right[i] = n if len(stack) == 0 else stack[-1]\n",
    "            stack.append(i)\n",
    "        area = 0\n",
    "        for i in range(n):\n",
    "            area = max(area, heights[i] * (right[i] - left[i] -  1))\n",
    "            print(i, left[i], right[i])\n",
    "        return area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "\n",
    "        n=len(heights)\n",
    "        heights=[-1]+heights+[-1]\n",
    "        print(heights)\n",
    "        stack=[]\n",
    "        res=[]\n",
    "        for i in range(n+2):\n",
    "            while stack and heights[stack[-1]]>heights[i]:\n",
    "                k=stack.pop()\n",
    "                h=heights[k]\n",
    "                wide=i-stack[-1]-1\n",
    "                s=wide*h\n",
    "                res.append(s)\n",
    "            stack.append(i)\n",
    "        return(max(res))\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        def min_lr(heights):\n",
    "            q=[]\n",
    "            a1=[]\n",
    "            for i in range(len(heights)):\n",
    "                while q and heights[q[-1]]>=heights[i]:\n",
    "                    q.pop()\n",
    "                # print(i,q)\n",
    "                a1.append(q[-1] if q else -1)\n",
    "                q.append(i)\n",
    "            return a1\n",
    "        a1 = min_lr(heights)\n",
    "        a2 = min_lr(heights[::-1])[::-1]\n",
    "\n",
    "        print(a1)\n",
    "        print(a2)\n",
    "        maxi=0\n",
    "        for i in range(len(heights)):\n",
    "            maxi=max(maxi, (len(heights)-a1[i]-a2[i]-2)*heights[i] )\n",
    "        return maxi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        boundl, boundr = [-1] * len(heights), [len(heights)] * len(heights)\n",
    "        \n",
    "        stack = []\n",
    "        for i in range(len(heights)):\n",
    "            while len(stack) > 0 and stack[-1][0] >= heights[i]:\n",
    "                boundr[stack.pop()[1]] = i\n",
    "            if len(stack) != 0:\n",
    "                boundl[i] = stack[-1][1]\n",
    "            stack.append((heights[i], i))\n",
    "        \n",
    "        # stack = []\n",
    "        # for i in range(len(heights) - 1, -1, -1):\n",
    "        #     while len(stack) > 0 and stack[-1][0] >= heights[i]:\n",
    "        #         stack.pop()\n",
    "        #     if len(stack) != 0:\n",
    "        #         boundr[i] = stack[-1][1]\n",
    "        #     stack.append((heights[i], i))\n",
    "        \n",
    "        print(boundl, boundr)\n",
    "        # [-1, -1, 1, 2, 1, 4] [1, 6, 4, 4, 6, 6]\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(len(heights)):\n",
    "            l = i - boundl[i] - 1\n",
    "            r = boundr[i] - i - 1\n",
    "            res = max(res, (l + r + 1) * heights[i])\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        def min_lr(heights):\n",
    "            q=[]\n",
    "            a1=[]\n",
    "            for i in range(len(heights)):\n",
    "                while q and heights[q[-1]]>=heights[i]:\n",
    "                    q.pop()\n",
    "                # print(i,q)\n",
    "                a1.append(q[-1] if q else -1)\n",
    "                q.append(i)\n",
    "            return a1\n",
    "        a1 = min_lr(heights)\n",
    "        a2 = min_lr(heights[::-1])[::-1]\n",
    "\n",
    "        # print(a1)\n",
    "        # print(a2)\n",
    "        maxi=0\n",
    "        for i in range(len(heights)):\n",
    "            maxi=max(maxi, (len(heights)-a1[i]-a2[i]-2)*heights[i] )\n",
    "        return maxi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        # 暴力超时\n",
    "        # n = len(heights)\n",
    "        # ans = 0\n",
    "        # for mid in range(n):  # 枚举中点\n",
    "        #     left, right = mid, mid\n",
    "        #     while left > 0 and heights[left-1] >= heights[mid]:\n",
    "        #         left -= 1\n",
    "        #     while right < n-1 and heights[mid] <= heights[right+1]:\n",
    "        #         right += 1\n",
    "        #     ans = max(ans, (right - left + 1) * heights[mid])\n",
    "        # return ans\n",
    "\n",
    "        # 暴力超时\n",
    "        # n = len(heights)\n",
    "        # ans = 0\n",
    "        # for left in range(n):\n",
    "        #     minHeight = float('inf')\n",
    "        #     for right in range(left, n):\n",
    "        #         minHeight = min(minHeight, heights[right])\n",
    "        #         ans = max(ans, (right - left + 1) * minHeight)\n",
    "        # return ans\n",
    "\n",
    "        n = len(heights)\n",
    "        left_index, right_index = [0] * n, [0] * n\n",
    "\n",
    "        my_stack = []\n",
    "        for i in range(n):\n",
    "            while len(my_stack) > 0 and heights[my_stack[-1]] >= heights[i]:\n",
    "                my_stack.pop()\n",
    "            left_index[i] = my_stack[-1] if len(my_stack)!= 0 else -1\n",
    "            my_stack.append(i)\n",
    "        \n",
    "        my_stack = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while len(my_stack) > 0 and heights[my_stack[-1]] >= heights[i]:\n",
    "                my_stack.pop()\n",
    "            right_index[i] = my_stack[-1] if len(my_stack)!= 0 else n\n",
    "            my_stack.append(i)\n",
    "        \n",
    "        print(left_index)\n",
    "        print(right_index)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            # if n > 0:\n",
    "            ans = max(ans, (right_index[i] - left_index[i] - 1) * heights[i])\n",
    "            # else:\n",
    "            #     ans = 0\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        heights = [-1] + heights + [0]\n",
    "        stack = []\n",
    "        length = len(heights)\n",
    "        ans = [0] * length\n",
    "\n",
    "        for i,height in enumerate(heights):\n",
    "            while stack and heights[stack[-1]] > height:\n",
    "                ans[stack[-1]] = heights[stack[-1]] * (i-1-stack[-2])\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return max(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        stack = []        \n",
    "        left, right = [-1] * n, [n] * n\n",
    "        for i, x in enumerate(heights):\n",
    "            while stack and stack[-1][0] >= x:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = stack[-1][1]\n",
    "            stack.append((x, i))\n",
    "        stack = []\n",
    "        for i, x in enumerate(reversed(heights)):\n",
    "            while stack and stack[-1][0] >= x:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right[n - 1 - i] = n - 1 - stack[-1][1]\n",
    "            stack.append((x, i))\n",
    "        return max(heights[i] * (right[i] - left[i] - 1) for i in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        left,right = [0]*n,[0]*n\n",
    "        \n",
    "        momo_stack = list()\n",
    "        for i in range(n):\n",
    "            while momo_stack and heights[momo_stack[-1]] >= heights[i]:\n",
    "                momo_stack.pop()\n",
    "            left[i] = momo_stack[-1] if momo_stack else -1\n",
    "            momo_stack.append(i)\n",
    "\n",
    "        momo_stack = list()\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while momo_stack and heights[momo_stack[-1]] >= heights[i]:\n",
    "                momo_stack.pop()\n",
    "            right[i] = momo_stack[-1] if momo_stack else n\n",
    "            momo_stack.append(i)\n",
    "        \n",
    "        print(left,right)\n",
    "        ans = max((right[i]-left[i]-1)*heights[i] for i in range(n)) if n > 0 else 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        #两次循环找出左右边界即可\n",
    "        #以左侧边界为例，如果左侧值比当前值高，那么当前值的左侧边界就是左侧值的左侧边界，反之就是自己\n",
    "        #最左边的左侧边界只能是自己\n",
    "        #右侧则是一样\n",
    "        left = [-1]\n",
    "        stack = [0]\n",
    "        for i in range(1,len(heights)):\n",
    "            while stack and heights[i] <= heights[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                left.append(-1)\n",
    "            else:\n",
    "                left.append(stack[-1])\n",
    "            stack.append(i)\n",
    "        right = [len(heights)]\n",
    "        stack = [len(heights)-1]\n",
    "        for i in range(1,len(heights)):\n",
    "            i = len(heights)-1-i\n",
    "            while stack and heights[i] <= heights[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                right.append(len(heights))\n",
    "            else:\n",
    "                right.append(stack[-1])\n",
    "            stack.append(i)\n",
    "        right = right[::-1]\n",
    "        print(left,right)\n",
    "        max1 = 0\n",
    "        for i in range(len(left)):\n",
    "            if (right[i] - left[i] - 1) * heights[i] > max1:\n",
    "                max1 = (right[i] - left[i] - 1) * heights[i]\n",
    "        return max1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        ans = 0\n",
    "        g = defaultdict(list)\n",
    "        n = len(heights)\n",
    "        sl = SortedList()\n",
    "        for i, x in enumerate(heights): g[x].append(i)\n",
    "        for x in sorted(set(heights)):\n",
    "            for i in g[x]:\n",
    "                p = sl.bisect_left(i)-1\n",
    "                l = sl[p] if 0 <= p < len(sl) else -1\n",
    "                p = sl.bisect_left(i)\n",
    "                r = sl[p] if 0 <= p < len(sl) else n\n",
    "                ans = max(ans, (r-l - 1) * x)\n",
    "            for i in g[x]: sl.add(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "\n",
    "\n",
    "        n = len(heights)\n",
    "        left, right =[0]* len(heights),[0] * len(heights)\n",
    "\n",
    "        ## 利用单调栈 求出 每个 柱子 左边 右边的 短板\n",
    "\n",
    "        mono_stack = []\n",
    "        mono_stack.append(0)\n",
    "\n",
    "        left[0] = -1\n",
    "\n",
    "        for i in range(1,len(heights)):\n",
    "            while mono_stack and  heights[i] <= heights[mono_stack[-1]]:\n",
    "                mono_stack.pop()\n",
    "\n",
    "            if not mono_stack:\n",
    "                left[i] = -1 \n",
    "            else:\n",
    "                left[i] = mono_stack[-1]\n",
    "            mono_stack.append(i)\n",
    "\n",
    "        mono_stack = []\n",
    "\n",
    "        mono_stack.append(len(heights) -1)\n",
    "        right[len(heights) - 1] = len(heights)\n",
    "\n",
    "        for i in range(len(heights)-2, -1, -1):\n",
    "            \n",
    "            while mono_stack and heights[i] <= heights[mono_stack[-1]]:\n",
    "                mono_stack.pop()\n",
    "\n",
    "            if not mono_stack:\n",
    "                right[i] = len(heights)\n",
    "            else:\n",
    "                right[i] = mono_stack[-1]\n",
    "            mono_stack.append(i)\n",
    "        print(left,right)\n",
    "        max_res = 0\n",
    "        for i in range(len(heights)):\n",
    "            if max_res < (right[i] - left[i] -1)*heights[i]:\n",
    "                max_res  = (right[i] - left[i] -1)*heights[i]\n",
    "\n",
    "        return max_res\n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = [(0, -1)]\n",
    "        heights.append(0)\n",
    "        res = 0\n",
    "        for i,height in enumerate(heights):\n",
    "            while stack and height < stack[-1][0]:\n",
    "                h = stack[-1][0]            # 长\n",
    "                w = i - stack[-2][1] - 1    # 宽\n",
    "                res = max(res, h*w)\n",
    "                stack.pop()                 # 栈顶元素已经求过面积，pop出来，换下一个元素\n",
    "            stack.append((height, i))       # 和栈顶元素比较之后，当前元素才可以入栈\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "\n",
    "        #if None\n",
    "        if not heights:\n",
    "            return 0\n",
    "\n",
    "        #init\n",
    "        res = 0\n",
    "        stack = [(0,-1)] #(init_height, inx)\n",
    "        heights.append(0)\n",
    "\n",
    "        #do traverse\n",
    "        for inx, hgt in enumerate(heights):\n",
    "            while stack:\n",
    "                top_elem_hgt = stack[-1][0]\n",
    "                # print('top_elem_hgt:\\t', top_elem_hgt)\n",
    "                if hgt >= top_elem_hgt:\n",
    "                    stack.append((hgt, inx))\n",
    "                    break\n",
    "                else:\n",
    "                    # print('stack:\\t', stack)\n",
    "                    # print('hgt:\\t', hgt)\n",
    "                    flag_inx = stack[-2][1]\n",
    "                    top_elem_hgt, top_inx = stack.pop()\n",
    "                    width = inx - flag_inx - 1\n",
    "                    # print('*******', inx, '*******')\n",
    "                    # print('top_elem_hgt:\\t', top_elem_hgt)\n",
    "                    # print('width:\\t', width)\n",
    "                    cur_area = (top_elem_hgt) * width\n",
    "                    # print('cur_area:\\t', cur_area)\n",
    "                    res = max(res, cur_area)\n",
    "            # print('stack:\\t', stack)\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "#         stack = [(0, -1)]\n",
    "#         heights.append(0)\n",
    "#         res = 0\n",
    "#         for i,height in enumerate(heights):\n",
    "#             while stack and height < stack[-1][0]:\n",
    "#                 h = stack[-1][0]            # 长\n",
    "#                 w = i - stack[-2][1] - 1    # 宽\n",
    "#                 print('*******', i, '*******')\n",
    "#                 print('hgt:\\t', h)\n",
    "#                 print('width:\\t', w)\n",
    "#                 res = max(res, h*w)\n",
    "#                 stack.pop()                 # 栈顶元素已经求过面积，pop出来，换下一个元素\n",
    "#                 print('res:\\t', res)\n",
    "#             stack.append((height, i))       # 和栈顶元素比较之后，当前元素才可以入栈\n",
    "#         return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = [-1]\n",
    "        n = len(heights)\n",
    "        Area = 0\n",
    "        for i in range(n):\n",
    "            while len(stack)>1 and heights[stack[-1]] > heights[i]:\n",
    "                \n",
    "                Area = max(Area,heights[stack[-1]]*(i-stack[-2]-1))\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        Area = max(Area,max([heights[stack[i]]*(n-stack[i-1]-1) for i in range(1,len(stack))]))\n",
    "               \n",
    "        return Area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = [(0, -1)]\n",
    "        heights.append(0)\n",
    "        res = 0\n",
    "        for i, height in enumerate(heights):\n",
    "            while stack and height < stack[-1][0]:\n",
    "                h = stack[-1][0] #高\n",
    "                w = i - stack[-2][1] - 1 #宽\n",
    "                res = max(res, h * w)\n",
    "                stack.pop () # 栈顶元素已经求过面积，pop出来，换下一个元素\n",
    "            stack.append((height,i))  # 和栈顶元素比较之后，当前元素才可以入栈\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n=len(heights)\n",
    "        left,right=[-1]*n,[n]*n\n",
    "        st=[]\n",
    "        for i in range(n):\n",
    "            while st and heights[st[-1]]>=heights[i]:\n",
    "                right[st[-1]]=i\n",
    "                st.pop()\n",
    "            if st:\n",
    "                left[i]=st[-1]\n",
    "            st.append(i)\n",
    "        return max([(right[i]-left[i]-1)*heights[i] for i in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        l = [-1] * n\n",
    "        r = [n] * n\n",
    "        s = []\n",
    "        for i in range(n):\n",
    "            while s and heights[s[-1]] > heights[i]:\n",
    "                idx = s.pop()\n",
    "                r[idx] = i\n",
    "            s.append(i)\n",
    "        \n",
    "        s = []\n",
    "        heights_reverse = heights[::-1]\n",
    "        for i in range(n):\n",
    "            while s and heights_reverse[s[-1]] > heights_reverse[i]:\n",
    "                idx = s.pop()\n",
    "                l[n-1-idx] = n-1-i\n",
    "            s.append(i)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            temp = heights[i]*(r[i]-l[i]-1)\n",
    "            res = max(res, temp)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        left = [0]*len(heights)\n",
    "        right = [0] *len(heights)\n",
    "\n",
    "        left_stack = []\n",
    "        j = 0\n",
    "        for i in range(1000000):\n",
    "            if left_stack:\n",
    "                if heights[j] > heights[left_stack[-1]]:\n",
    "                    left[j] = j - left_stack[-1] - 1\n",
    "                    left_stack.append(j)\n",
    "                    j += 1\n",
    "                else:\n",
    "                    left_stack.pop()\n",
    "            else:\n",
    "                left[j] = j\n",
    "                left_stack.append(j)\n",
    "                j += 1\n",
    "            if j == len(heights):\n",
    "                break\n",
    "\n",
    "        right_stack = []\n",
    "        j = len(heights)-1\n",
    "        for i in range(1000000):\n",
    "            if right_stack:\n",
    "                if heights[j] > heights[right_stack[-1]]:\n",
    "                    right[j] = right_stack[-1] - j - 1\n",
    "                    right_stack.append(j)\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    right_stack.pop()\n",
    "            else:\n",
    "                right[j] = len(heights)-1 - j\n",
    "                right_stack.append(j)\n",
    "                j -= 1\n",
    "            if j == -1:\n",
    "                break\n",
    "        \n",
    "        maxi = 0\n",
    "        for i in range(len(heights)):\n",
    "            aa = heights[i] * (1+left[i]+right[i])\n",
    "            maxi = max(maxi, aa)\n",
    "\n",
    "        return maxi    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        max_v = 0\n",
    "        def f(h):\n",
    "            a = [-1 for _ in range(len(h))]\n",
    "            stack = []\n",
    "            for i in range(len(h)):\n",
    "                if len(stack) == 0:\n",
    "                    stack.append(i)\n",
    "                    continue\n",
    "                if h[i] > h[stack[-1]]:\n",
    "                    stack.append(i)\n",
    "                else:\n",
    "                    while len(stack)!= 0 and h[i] <= h[stack[-1]]:\n",
    "                        a[stack[-1]] = stack[-2] if len(stack) >= 2 else -1\n",
    "                        del stack[-1]\n",
    "                    stack.append(i)\n",
    "            return a[:-1]\n",
    "        heights.append(-1)\n",
    "        a = f(heights)\n",
    "        del heights[-1]\n",
    "        heights = heights[::-1]\n",
    "        heights.append(-1)\n",
    "        b = [len(heights)-1-item - 1 for item in f(heights)[::-1]]\n",
    "        print(a,b)\n",
    "        del heights[-1]\n",
    "        heights = heights[::-1]\n",
    "        for i in range(len(a)):\n",
    "            tmp = (b[i]-a[i]-1)*heights[i]\n",
    "            if tmp > max_v:\n",
    "                max_v = tmp\n",
    "        return max_v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        left, right = [0] * n, [n] * n\n",
    "\n",
    "        mono_stack = list()\n",
    "        \n",
    "        for i in range(n):\n",
    "            while mono_stack and heights[mono_stack[-1]]>=heights[i]:\n",
    "                right[mono_stack[-1]] = i\n",
    "                mono_stack.pop()\n",
    "            left[i] = mono_stack[-1] if mono_stack else -1\n",
    "            mono_stack.append(i)\n",
    "        ans = [(right[i]-1-left[i])*heights[i] for i in range(n)]\n",
    "        return max(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        # 对于每个idx，要找到以他为最短板可以左右衍生多少\n",
    "        # 单调栈，保存最小的\n",
    "        stack = [[-1,-1]]\n",
    "        n = len(heights)\n",
    "        left = [0] * n\n",
    "        for i in range(n):\n",
    "            while stack:\n",
    "                if heights[i] <= stack[-1][0]:\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    break\n",
    "            # print(heights[i],stack)\n",
    "            left[i] = i - stack[-1][1] - 1\n",
    "            stack.append([heights[i], i])\n",
    "        right = [0] * n\n",
    "        stack = [[-1,n]]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while heights[i] <= stack[-1][0]:\n",
    "                stack.pop()\n",
    "            right[i] = stack[-1][1] - i - 1\n",
    "            stack.append([heights[i],i])\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, heights[i] * (1 + left[i] + right[i]))\n",
    "                \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        if(n==0):\n",
    "            return 0\n",
    "        elif(n==1):\n",
    "            return heights[0]\n",
    "        left, right = [0]*n, [0]*n\n",
    "        min_stack = []\n",
    "        for i in range(n):\n",
    "            while(min_stack and heights[min_stack[-1]] >= heights[i]):\n",
    "                min_stack.pop()\n",
    "            left[i] = min_stack[-1] if min_stack else -1\n",
    "            min_stack.append(i)\n",
    "        min_stack = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while(min_stack and heights[min_stack[-1]] >= heights[i]):\n",
    "                min_stack.pop()\n",
    "            right[i] = min_stack[-1] if min_stack else n\n",
    "            min_stack.append(i)\n",
    "            \n",
    "        return max([(right[i]-1-left[i]) * heights[i] for i in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "\n",
    "        mono_stack = []\n",
    "        for i in range(n):\n",
    "            while mono_stack and heights[mono_stack[-1]] >= heights[i]:\n",
    "                mono_stack.pop()\n",
    "            left[i] = mono_stack[-1] if mono_stack else -1\n",
    "            mono_stack.append(i)\n",
    "        \n",
    "        mono_stack = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while mono_stack and heights[mono_stack[-1]] >= heights[i]:\n",
    "                mono_stack.pop()\n",
    "            right[i] = mono_stack[-1] if mono_stack else n\n",
    "            mono_stack.append(i)\n",
    "        \n",
    "        return max([(right[i]-left[i]-1) * heights[i] for i in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and heights[stack[-1]] >= heights[i]:\n",
    "                stack.pop()\n",
    "            left[i] = stack[-1] if stack else -1\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while stack and heights[stack[-1]] >= heights[i]:\n",
    "                stack.pop()\n",
    "            right[i] = stack[-1] if stack else n\n",
    "            stack.append(i)\n",
    "        return max([(right[i]-left[i]-1) * heights[i] for i in range(n)])\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        st = []\n",
    "        left, right = [0] * n, [0] * n\n",
    "        \n",
    "        for idx in range(n):\n",
    "            while st and heights[st[-1]] >= heights[idx]:\n",
    "                # st_l[st[-1]] = idx\n",
    "                st.pop()\n",
    "                \n",
    "            if not st:\n",
    "                left[idx] = -1\n",
    "            else: \n",
    "                left[idx] = st[-1]\n",
    "            st.append(idx)\n",
    "\n",
    "        st = []\n",
    "        for idx in range(n - 1, -1, -1):\n",
    "            while st and heights[st[-1]] >= heights[idx]:\n",
    "                # st_l[st[-1]] = idx\n",
    "                st.pop()\n",
    "                \n",
    "            if not st:\n",
    "                right[idx] = n\n",
    "            else: \n",
    "                right[idx] = st[-1]\n",
    "            st.append(idx)\n",
    "        # print(left, right)\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            # print(right, left)\n",
    "            ans.append(heights[i] * (right[i] - left[i] - 1))\n",
    "\n",
    "        return max(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        stack = []\n",
    "        left, right = [0] * n, [n] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            while stack and heights[stack[-1]] >= heights[i]:\n",
    "                right[stack[-1]] = i\n",
    "                stack.pop()\n",
    "            left[i] = stack[-1] if stack else -1\n",
    "            stack.append(i)\n",
    "        return max([(right[i] - left[i]-1) * heights[i] for i in range(n)]) if n > 0 else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        st = [[-1,-1]]\n",
    "        heights.append(0)\n",
    "        res = 0\n",
    "        for i,h in enumerate(heights):\n",
    "            while st and h < st[-1][0]:\n",
    "                he = st.pop()[0]\n",
    "                we = st[-1][1]\n",
    "                res = max(res,he * (i - we - 1))\n",
    "            st.append([h,i])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "\n",
    "#         maxx,n=0,len(heights)\n",
    "#         if len(set(heights))==1:\n",
    "#             return heights[0]*n\n",
    "#         for i in range(n):\n",
    "#             l,r=0,0\n",
    "#             for j in range(i-1,-1,-1):\n",
    "#                 if heights[j]<heights[i]:\n",
    "#                     break\n",
    "#                 l+=1\n",
    "#             for k in range(i+1,n):\n",
    "#                 if heights[k]<heights[i]:\n",
    "#                     break\n",
    "#                 r+=1\n",
    "#             maxx=max(maxx,heights[i]*(l+r+1))\n",
    "#         return maxx\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, h: List[int]) -> int:\n",
    "        stk = []\n",
    "        n = len(h)\n",
    "        left = [0 for i in range(n)]\n",
    "        right = [0 for i in range(n)]\n",
    "        \n",
    "        for i in range(n):\n",
    "            while len(stk) > 0 and h[stk[-1]] >= h[i]:\n",
    "                stk.pop()\n",
    "            if len(stk) == 0:\n",
    "                left[i] = 0 \n",
    "            else:\n",
    "                left[i] = stk[-1] + 1\n",
    "            stk.append(i) \n",
    "\n",
    "        stk = [] \n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while len(stk) > 0 and h[stk[-1]] >= h[i]:\n",
    "                stk.pop()\n",
    "            if len(stk) == 0:\n",
    "                right[i] = n + 1\n",
    "            else:\n",
    "                right[i] = stk[-1] + 1\n",
    "            stk.append(i)\n",
    "\n",
    "        ans = -2**31\n",
    "        for i in range(n):\n",
    "            ans = max(ans, h[i] * (right[i] - left[i] - 1))\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        # 左边比我小的最远位置, 向前遍历\n",
    "        leftStk = []\n",
    "        leftLT = [-1] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            h = heights[i]\n",
    "            while leftStk and h < heights[leftStk[-1]]:\n",
    "                idx = leftStk.pop()\n",
    "                leftLT[idx] = i\n",
    "            leftStk.append(i)\n",
    "\n",
    "        # 右边比我小的最远位置, 向后遍历\n",
    "        rightStk = []\n",
    "        rightLT = [n] * n\n",
    "        for i in range(n):\n",
    "            h = heights[i]\n",
    "            while rightStk and h < heights[rightStk[-1]]:\n",
    "                idx = rightStk.pop()\n",
    "                rightLT[idx] = i\n",
    "            rightStk.append(i)\n",
    "\n",
    "        maxArea = 0\n",
    "        curArea = 0\n",
    "        for i in range(n):\n",
    "            curArea = heights[i] * (rightLT[i] - leftLT[i] - 1)\n",
    "            maxArea = max(maxArea, curArea)\n",
    "        return maxArea"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Data:\n",
    "    def __init__(self, idx, height):\n",
    "        self.idx = idx\n",
    "        self.height = height\n",
    "\n",
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.data = []\n",
    "        self.end_idx = -1\n",
    "\n",
    "    def clean(self):\n",
    "        self.data = []\n",
    "        self.end_idx = -1\n",
    "\n",
    "    def pop(self):\n",
    "        if self.end_idx >= 0:\n",
    "            self.end_idx = self.end_idx - 1\n",
    "            return self.data[self.end_idx + 1]\n",
    "        else:\n",
    "            return None\n",
    "        \n",
    "    def push(self, data):\n",
    "        self.end_idx = self.end_idx + 1\n",
    "        if len(self.data) - 1 >= self.end_idx:\n",
    "            self.data[self.end_idx] = data\n",
    "        else:\n",
    "            self.data.append(data)\n",
    "\n",
    "    def top(self):\n",
    "        if self.end_idx >= 0:\n",
    "            return self.data[self.end_idx]\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "    def size(self):\n",
    "        return self.end_idx + 1\n",
    "\n",
    "\n",
    "def check(ss, idx, h):\n",
    "    if ss.size() == 0:\n",
    "        ss.push(Data(idx, h))\n",
    "        return ss, -1\n",
    "    elif ss.top().height < h:\n",
    "        out_idx = ss.top().idx\n",
    "        ss.push(Data(idx, h))\n",
    "        return ss, out_idx\n",
    "    else:\n",
    "        ss.pop()\n",
    "        return check(ss, idx, h)\n",
    "    \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "\n",
    "        ss = Stack()\n",
    "        left = [-1 for i in range(len(heights))]\n",
    "        for i in range(len(heights)):\n",
    "            ss, left[i] = check(ss, i, heights[i])\n",
    "            # for ii in range(ss.end_idx):\n",
    "            #     print(ss.data[ii].height, ss.data[ii].idx)\n",
    "            # print()\n",
    "        \n",
    "        ss = Stack()\n",
    "        right = [-1 for i in range(len(heights))]\n",
    "        for i in range(len(heights)-1, -1, -1):\n",
    "            ss, right[i] = check(ss, i, heights[i])\n",
    "            if right[i] < 0:\n",
    "                right[i] = len(heights)\n",
    "\n",
    "        area = [heights[i] * (right[i] - left[i] - 1) for i in range(len(heights))]\n",
    "\n",
    "        max_area = 0\n",
    "        for i in range(len(heights)):\n",
    "            max_area = max(max_area, area[i])\n",
    "\n",
    "        # print(left)\n",
    "        # print(right)\n",
    "        # print(area)\n",
    "\n",
    "        return max_area\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        left=[0]*len(heights)\n",
    "        right=[0]*len(heights)\n",
    "        stack=[]\n",
    "        for i in range(len(heights)):\n",
    "            while stack and heights[stack[-1]]>=heights[i]:\n",
    "                stack.pop()\n",
    "            left[i]=stack[-1] if stack else -1\n",
    "            stack.append(i)\n",
    "        stack=[]\n",
    "        for j in range(len(heights)-1,-1,-1):\n",
    "            while stack and heights[stack[-1]]>=heights[j]:\n",
    "                stack.pop()\n",
    "            right[j]=stack[-1] if stack else len(heights)\n",
    "            stack.append(j)\n",
    "        return max([(right[i]-left[i]-1)*heights[i] for i in range(len(heights))])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        left,right = [],[]\n",
    "        stack = [-1]\n",
    "        n = len(heights)\n",
    "        for i in range(n):\n",
    "            while len(stack)>1 and heights[stack[-1]] >= heights[i]:\n",
    "                stack.pop()\n",
    "            left.append(stack[-1])\n",
    "            stack.append(i)\n",
    "        stack1 = [n]\n",
    "        for j in range(n-1,-1,-1):\n",
    "            while len(stack1)>1 and heights[stack1[-1]] >= heights[j]:\n",
    "                stack1.pop()\n",
    "            right.append(stack1[-1])\n",
    "            stack1.append(j)\n",
    "        \n",
    "        Area = [(right[n-i-1]-left[i]-1)*heights[i] for i in range(n)]\n",
    "\n",
    "\n",
    "        \n",
    "        return max(Area)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        left,right = [],[]\n",
    "        stack = [-1]\n",
    "        n = len(heights)\n",
    "        for i in range(n):\n",
    "            while len(stack)>1 and heights[stack[-1]] >= heights[i]:\n",
    "                stack.pop()\n",
    "            left.append(stack[-1])\n",
    "            stack.append(i)\n",
    "        stack1 = [n]\n",
    "        for j in range(n-1,-1,-1):\n",
    "            while len(stack1)>1 and heights[stack1[-1]] >= heights[j]:\n",
    "                stack1.pop()\n",
    "            right.append(stack1[-1])\n",
    "            stack1.append(j)\n",
    "        \n",
    "        Area = [(right[n-i-1]-left[i]-1)*heights[i] for i in range(n)]\n",
    "\n",
    "\n",
    "        \n",
    "        return max(Area)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        stack = []\n",
    "        left = []\n",
    "        for i in range(n):\n",
    "            while stack and heights[stack[-1]]>=heights[i]:\n",
    "                stack.pop()\n",
    "            if len(stack) == 0:\n",
    "                left.append(-1)\n",
    "            else:\n",
    "                left.append(stack[-1])\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        right = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while stack and heights[stack[-1]] >= heights[i]:\n",
    "                stack.pop()\n",
    "            if len(stack) == 0:\n",
    "                right.insert(0,n)\n",
    "            else:\n",
    "                right.insert(0,stack[-1])\n",
    "            stack.append(i)\n",
    "        res_list = [(right[i]-left[i]-1)*heights[i] for i in range(n)]\n",
    "        # print(left)\n",
    "        # print(right)\n",
    "        # print(res_list)\n",
    "        res = max(res_list)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n=len(heights)\n",
    "        stack=[0]\n",
    "        left=[-1]*n\n",
    "        right=[n]*n\n",
    "        for i in range(1,n):\n",
    "            while stack and heights[stack[-1]]>heights[i]:\n",
    "                right[stack.pop()]=i\n",
    "            if stack:\n",
    "                left[i]=stack[-1]    \n",
    "            stack.append(i)\n",
    "        return max([(right[i]-left[i]-1)*heights[i] for i in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        def do(heights):\n",
    "            if len(heights) == 1:\n",
    "                return heights[0]\n",
    "            q = [[0, heights[0]]]\n",
    "            res = heights[0]\n",
    "            for i, h in enumerate(heights):\n",
    "                if i == 0:\n",
    "                    continue\n",
    "                if len(q) == 0 or h >= q[-1][1]:\n",
    "                    q.append([i, h])\n",
    "                else:\n",
    "                    while len(q)>0 and h < q[-1][1]:\n",
    "                        start, starth = q.pop()\n",
    "                        if len(q) > 0:\n",
    "                            end = q[-1][0]\n",
    "                        else:\n",
    "                            end = -1\n",
    "                        res = max(res, starth * (i - end - 1))\n",
    "                    q.append([i, h])\n",
    "            if len(q) > 0:\n",
    "                end = len(heights)\n",
    "                for i, x in enumerate(q):\n",
    "                    c, ch = x\n",
    "                    if i == 0:\n",
    "                        res = max(res, q[0][1] * end)\n",
    "                    else:\n",
    "                        res = max(res, ch * (end - q[i-1][0]-1))    \n",
    "            return res\n",
    "        return do(heights)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        ansr = [1] * len(heights)\n",
    "        ansl = [1] * len(heights)\n",
    "\n",
    "        stackr = []\n",
    "        heights.append(-1)\n",
    "        for idx in range(len(heights)):\n",
    "            while stackr  and heights[stackr[-1]] > heights[idx]:\n",
    "                aa = stackr.pop()\n",
    "                ansr[aa] = idx - aa\n",
    "            \n",
    "            stackr.append(idx)\n",
    "            # print(stackr, ansr)\n",
    "        stackl = []\n",
    "        heights.pop()\n",
    "        tmp = heights\n",
    "        heights = [-1]\n",
    "        heights.extend(tmp)\n",
    "        for idx in range(len(heights) - 1, -1, -1):\n",
    "            while stackl and heights[stackl[-1]] > heights[idx]:\n",
    "                aa = stackl.pop()\n",
    "                \n",
    "                ansl[aa - 1] = aa - idx\n",
    "            stackl.append(idx)\n",
    "        print(ansr)\n",
    "        print(ansl)\n",
    "        for i in range(len(ansr)):\n",
    "            ansr[i] = heights[i + 1] * (ansl[i] + ansr[i] - 1)\n",
    "        return max(ansr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        显然的单调栈应用\n",
    "        \"\"\"\n",
    "        ans = 0\n",
    "\n",
    "        stk = []\n",
    "        for i, height in enumerate(heights):\n",
    "            pw = 0  # 当前位置之前的宽度\n",
    "            while stk and heights[stk[-1][0]] > height:\n",
    "                j, w = stk.pop()\n",
    "                pw += w+1\n",
    "                ans = max(ans, heights[j]*(i-j+w))\n",
    "            stk.append((i, pw))\n",
    "\n",
    "        for i, w in stk:\n",
    "            h = heights[i]\n",
    "            ans = max(ans, h*(stk[-1][0] - i + 1 + w))\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        arr = [0] + heights + [0]\n",
    "        ans, stack = 0, []\n",
    "        for index, v in enumerate(arr):\n",
    "            while stack and v < stack[-1][1]:\n",
    "                index_, v_ = stack.pop()\n",
    "                ans = max(ans, v_*(index-stack[-1][0]-1))\n",
    "            stack.append((index, v))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        heights.append(0)\n",
    "        stack = deque()\n",
    "        stack.append((0,-1))\n",
    "        maximum = 0\n",
    "        for i in range(len(heights)):\n",
    "            while stack and stack[-1][0] > heights[i]:\n",
    "                maximum = max(maximum, stack[-1][0] * (i - stack[-2][1] - 1))\n",
    "                stack.pop()  \n",
    "            stack.append((heights[i],i))\n",
    "\n",
    "        return maximum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = [(-1, -1)]\n",
    "        result = 0\n",
    "        index = 0\n",
    "        for index, height in enumerate(heights):\n",
    "            while height < stack[-1][0]:\n",
    "                result = max(result, (index - stack[-2][1] - 1) * (stack[-1][0]))\n",
    "                stack.pop()\n",
    "            stack.append((height, index))\n",
    "        while stack[-1][0] != -1:\n",
    "            result = max(result, (index + 1 - stack[-2][1] - 1) * (stack[-1][0]))\n",
    "            stack.pop()\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        ans = 0\n",
    "        s = [(-1, 0)]\n",
    "        for i, h in enumerate(heights + [0]):\n",
    "            while s[-1][1] > h:\n",
    "                _, prev_h = s.pop()\n",
    "                area_i = (i-s[-1][0]-1) * prev_h\n",
    "                ans = max(ans, area_i)\n",
    "            \n",
    "            s.append((i, h))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        if n == 1:\n",
    "            return heights[0]\n",
    "        arr = [0] + heights + [0]\n",
    "        ans, stack = 0, []\n",
    "        for index, item in enumerate(arr):\n",
    "            while stack and item < stack[-1][1]:\n",
    "                _, _v = stack.pop()\n",
    "                ans = max(ans, _v*(index-stack[-1][0] - 1))\n",
    "            stack.append((index, item))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        heights = [0] + heights + [0]\n",
    "\n",
    "        stack = []\n",
    "        max_size = 0\n",
    "        for i, height in enumerate(heights):\n",
    "            if not stack:\n",
    "                stack.append([i, height])\n",
    "                continue\n",
    "            if stack[-1][1] > height:\n",
    "                while stack[-1][1] > height:\n",
    "                    p = stack.pop()\n",
    "                    cur_size = p[1] * (i-stack[-1][0]-1)\n",
    "                    max_size = max(max_size, cur_size)\n",
    "                stack.append([i,height])\n",
    "            else:\n",
    "                stack.append([i, height])\n",
    "        return max_size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        right = [n] * n\n",
    "        queue = []\n",
    "        for i, h in enumerate(heights):\n",
    "            while queue and queue[-1][0] > h:\n",
    "                curh, curi = queue.pop()\n",
    "                right[curi] = i\n",
    "            queue.append([h, i])\n",
    "        left = [-1] * n\n",
    "        queue = []\n",
    "        for j in range(n - 1, -1, -1):\n",
    "            h = heights[j]\n",
    "            while queue and queue[-1][0] > h:\n",
    "                curh, curj = queue.pop()\n",
    "                left[curj] = j\n",
    "            queue.append([h, j])\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            lefti = left[i]\n",
    "            righti = right[i]\n",
    "            cur = heights[i] + (i - lefti - 1) * heights[i] + (right[i] - i - 1) * heights[i]\n",
    "            ans = max(cur, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        res = 0\n",
    "        heights.append(0)\n",
    "        stack = []\n",
    "        for idx, h in enumerate(heights):\n",
    "            last_idx = idx\n",
    "            while stack and stack[-1][0] > h:\n",
    "                last_h, last_idx = stack.pop()\n",
    "                res = max(res, last_h * (idx - last_idx))\n",
    "            stack.append([h, last_idx])\n",
    "            # print(stack, idx, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        heights = [0] + heights + [0]\n",
    "        ans, stack = 0, [] # (idx, height)\n",
    "\n",
    "        for idx, height in enumerate(heights):\n",
    "            while stack and height < stack[-1][1]:\n",
    "                pre_idx, pre_height = stack.pop()\n",
    "                ans = max(ans, (idx - stack[-1][0] - 1) * pre_height) # 新遍历到的，与再前一个，夹逼一下\n",
    "            stack.append((idx, height))\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        heights = [0] + heights + [0]\n",
    "        ans, stack = 0, [] # (idx, height)\n",
    "\n",
    "        for idx, height in enumerate(heights):\n",
    "            while stack and height < stack[-1][1]:\n",
    "                pre_idx, pre_height = stack.pop()\n",
    "                ans = max(ans, (idx - stack[-1][0] - 1) * pre_height) # 新遍历到的，与再前一个，夹逼一下\n",
    "            stack.append((idx, height))\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = [(0, -1)]\n",
    "        heights.append(0)\n",
    "        res = 0\n",
    "        for i,height in enumerate(heights):\n",
    "            while stack and height < stack[-1][0]:\n",
    "                h = stack[-1][0]            # 长\n",
    "                w = i - stack[-2][1] - 1    # 宽\n",
    "                res = max(res, h*w)\n",
    "                stack.pop()                 # 栈顶元素已经求过面积，pop出来，换下一个元素\n",
    "            stack.append((height, i))       # 和栈顶元素比较之后，当前元素才可以入栈\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = [(-1, 0)]\n",
    "        heights.append(0)\n",
    "        res = 0\n",
    "        for i,height in enumerate(heights):\n",
    "            while stack and height < stack[-1][1]:\n",
    "                h = stack[-1][1]            # 长\n",
    "                w = i - stack[-2][0] - 1    # 宽\n",
    "                res = max(res, h*w)\n",
    "                stack.pop()                 # 栈顶元素已经求过面积，pop出来，换下一个元素\n",
    "            stack.append((i, height))       # 和栈顶元素比较之后，当前元素才可以入栈\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = [(0, -1)]\n",
    "        heights.append(0)\n",
    "        res = 0\n",
    "        for i,height in enumerate(heights):\n",
    "            while stack and height < stack[-1][0]:\n",
    "                h = stack[-1][0]            # 长\n",
    "                w = i - stack[-2][1] - 1    # 宽\n",
    "                res = max(res, h*w)\n",
    "                stack.pop()                 # 栈顶元素已经求过面积，pop出来，换下一个元素\n",
    "            stack.append((height, i))       # 和栈顶元素比较之后，当前元素才可以入栈\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sortedcontainers\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        l = sorted((h, p) for p, h in enumerate(heights))\n",
    "        place = sortedcontainers.SortedList([-1, len(heights)])\n",
    "        res = 0\n",
    "        for h, p in l:\n",
    "            p1 = place.bisect(p)\n",
    "            res = max(res, h*(place[p1]-place[p1-1]-1) )\n",
    "            place.add(p)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        heights = [-1]+heights+[-1]\n",
    "        n = len(heights)\n",
    "        left, right = [0]*n, [0]*n\n",
    "        stackl, stackr = [], []\n",
    "        for i in range(n):\n",
    "            while stackr and heights[stackr[-1]]>heights[i]:\n",
    "                tmpr = stackr.pop()\n",
    "                right[tmpr] = i-tmpr\n",
    "            while stackl and heights[stackl[-1]]>heights[n-i-1]:\n",
    "                tmpl = stackl.pop()\n",
    "                left[tmpl] = tmpl-(n-i-1)\n",
    "            stackr.append(i)\n",
    "            stackl.append(n-i-1)\n",
    "        res = 0\n",
    "        # print(left,right)\n",
    "        for i in range(1,n-1):\n",
    "            res = max(res,(right[i]+left[i]-1)*heights[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = []\n",
    "        heights = [0] + heights + [0]\n",
    "        left = [0] * len(heights)\n",
    "        for i in range(len(heights)):\n",
    "            if not stack:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                if heights[i] >= heights[stack[-1]]:\n",
    "                    stack.append(i)\n",
    "                else:\n",
    "                    while stack and heights[i] < heights[stack[-1]]:\n",
    "                        prev = stack.pop()\n",
    "                        left[prev] = i - prev\n",
    "                    stack.append(i)\n",
    "        right = [0] * len(heights)\n",
    "        for i in range(len(heights)-1, -1, -1):\n",
    "            if not stack:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                if heights[i] >= heights[stack[-1]]:\n",
    "                    stack.append(i)\n",
    "                else:\n",
    "                    while stack and heights[i] < heights[stack[-1]]:\n",
    "                        prev = stack.pop()\n",
    "                        right[prev] = prev - i\n",
    "                    stack.append(i)\n",
    "        max_area = 0\n",
    "        for i in range(1, len(heights)-1):\n",
    "            width = right[i] + left[i] - 1\n",
    "            max_area = max(max_area, width * heights[i])\n",
    "        return max_area\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        heights = heights + [0]\n",
    "        stk = []\n",
    "        stk.append([0, 0])\n",
    "        res = 0\n",
    "        for i, val in enumerate(heights, 1): #(index, val) \n",
    "            while val < stk[-1][1]:\n",
    "                cur = stk.pop()\n",
    "                area = cur[1] * (i - stk[-1][0] - 1)\n",
    "                res = max(res, area)\n",
    "            stk.append([i, val])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack, ans = [], 0\n",
    "        for i, h in enumerate(heights + [0]):\n",
    "            while stack and heights[stack[-1]] >= h:\n",
    "                H = heights[stack.pop()]\n",
    "                W = i if not stack else i-stack[-1]-1\n",
    "                ans = max(ans, H*W)\n",
    "            stack.append(i)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: 'List[int]') -> 'int':\n",
    "        ans = 0\n",
    "\n",
    "        if not heights:\n",
    "            return ans\n",
    "\n",
    "        n = len(heights)\n",
    "\n",
    "        for j in range(n):\n",
    "            if j + 1 < n and heights[j] <= heights[j + 1]:\n",
    "                continue\n",
    "\n",
    "            mini = float('inf')\n",
    "\n",
    "            for i in range(j, -1, -1):\n",
    "                mini = min(mini, heights[i])\n",
    "                ans = max(ans, mini * (j - i + 1))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights):\n",
    "        \"\"\"\n",
    "        :type heights: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(heights) == 0:\n",
    "            return 0\n",
    "        stk = []\n",
    "        max_area = 0\n",
    "        heights.append(0)\n",
    "        for i in range(len(heights)):\n",
    "            if (not stk) or (heights[i] >= stk[-1]):\n",
    "                stk.append(heights[i])\n",
    "            else:\n",
    "                count = 0\n",
    "                while stk and heights[i] < stk[-1]:\n",
    "                    count += 1\n",
    "                    if stk[-1] * count > max_area:\n",
    "                        max_area = stk[-1] * count\n",
    "                    stk.pop()\n",
    "                for k in range(count+1):\n",
    "                    stk.append(heights[i])\n",
    "        \n",
    "        # n = len(heights)\n",
    "        # for j in range(len(stk)):\n",
    "        #     if stk[j] * (n-j) > max_area:\n",
    "        #         max_area = stk[j] *(n-j)\n",
    "        \n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights):\n",
    "        \"\"\"\n",
    "        :type heights: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not heights:\n",
    "            return 0\n",
    "            \n",
    "        res = 0\n",
    "        stack = []\n",
    "        heights.append(-1)\n",
    "        for i in range(len(heights)):\n",
    "            current = heights[i]\n",
    "            while len(stack) != 0 and current <= heights[stack[-1]]:\n",
    "                h = heights[stack.pop()]\n",
    "                w = i if len(stack) == 0 else i - stack[-1] - 1\n",
    "                res = max(res, h * w)\n",
    "            stack.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: 'List[int]') -> 'int':\n",
    "        heights.append(0)\n",
    "        stack = [-1]\n",
    "        res = 0\n",
    "        for i in range(len(heights)):\n",
    "            while heights[i] < heights[stack[-1]]:\n",
    "                h = heights[stack.pop()]\n",
    "                w = i - stack[-1] - 1\n",
    "                res = max(res, h * w)\n",
    "            stack.append(i)\n",
    "        heights.pop()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights):\n",
    "        \"\"\"\n",
    "        :type heights: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        max_area = 0\n",
    "        if not heights:\n",
    "            return max_area\n",
    "        elif len(heights) == 1:\n",
    "            return heights[0]\n",
    "        starts, candidates = [], []\n",
    "        for idx, h in enumerate(heights):\n",
    "            if not candidates or candidates[-1] < h: \n",
    "                candidates.append(h)\n",
    "                starts.append(idx)\n",
    "            elif candidates[-1] > h:\n",
    "                while candidates and candidates[-1] > h:\n",
    "                    ended, last_pop_start = candidates.pop(), starts.pop()\n",
    "                    max_area = max(max_area, ended * (idx - last_pop_start))\n",
    "                candidates.append(h)\n",
    "                starts.append(last_pop_start)\n",
    "        # now inspect all the remaining rectangles\n",
    "        n = len(heights)\n",
    "        return max(max_area, max([candidate * (n - start) for candidate, start\n",
    "                                  in zip(candidates, starts)]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights):\n",
    "        \"\"\"\n",
    "        :type heights: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if heights == None:\n",
    "            return 0\n",
    "        stack = []\n",
    "        heights.append(-1)\n",
    "        ans = 0\n",
    "        \n",
    "        for i in range(len(heights)):\n",
    "            cur = heights[i]\n",
    "            if len(stack) == 0 or cur >= heights[stack[-1]]:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                while len(stack) != 0 and cur <= heights[stack[-1]]:\n",
    "                    h = heights[stack.pop()]\n",
    "                    left = stack[-1] if len(stack) != 0 else -1\n",
    "                    ans = max(ans, h * (i - left - 1))\n",
    "            stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights):\n",
    "        \"\"\"\n",
    "        :type heights: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \"\"\"\n",
    "        # 暴力解法, 超时\n",
    "        l = len(heights)\n",
    "        max_area = 0\n",
    "        for i in range(l):\n",
    "            height_min = 100000000000\n",
    "            for j in range(i, l):\n",
    "                height_min = min(height_min, heights[j])\n",
    "                max_area = max(max_area, height_min*(j-i+1))\n",
    "        return max_area\n",
    "        \"\"\"\n",
    "        l = len(heights)\n",
    "        if l == 0:\n",
    "            return 0\n",
    "        if l == 1:\n",
    "            return heights[0] * 1\n",
    "        left = [0] * len(heights)\n",
    "        right = [0] * len(heights)\n",
    "        left[0] = -1\n",
    "        for i in range(1, l):\n",
    "            if heights[i] > heights[i-1]:\n",
    "                left[i] = i - 1\n",
    "            else:\n",
    "                j = left[i-1]\n",
    "                tmp = heights[i]\n",
    "                while (j >= 0 and  heights[j] >= tmp) or j == -1:\n",
    "                    if j == -1:\n",
    "                        left[i] = -1\n",
    "                        break\n",
    "                    j = j - 1\n",
    "                left[i] = j\n",
    "        right[l-1] = l\n",
    "        for i in range(l-2, -1,-1):\n",
    "            if heights[i] > heights[i+1]:\n",
    "                right[i] = i + 1\n",
    "            else:\n",
    "                j = right[i+1]\n",
    "                tmp = heights[i]\n",
    "                while (j <= l-1 and  heights[j] >= tmp) or j == l:\n",
    "                    if j == l:\n",
    "                        right[i] = l\n",
    "                        break\n",
    "                    j = j + 1\n",
    "                right[i] = j\n",
    "        max_area = 0\n",
    "        for i in range(l):\n",
    "            max_area = max(max_area, (right[i]-left[i]-1)*heights[i])\n",
    "        print(left)\n",
    "        print(right)\n",
    "        return max_area\n",
    "        \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    DP based on Exhaustive algorithms to reduce redundancy\n",
    "    @param height, a list of integer\n",
    "    @return an integer\n",
    "    \"\"\"\n",
    "    def largestRectangleArea(self, height):\n",
    "        lens = len(height)\n",
    "        left = [1] * lens\n",
    "        right = [1] * lens\n",
    "        for i in range(lens):\n",
    "            j = i -1\n",
    "            while j >=0:\n",
    "                if height[j] >= height[i]:\n",
    "                    left[i]+=left[j]\n",
    "                    j-=left[j]\n",
    "                else:\n",
    "                    break\n",
    "        for i in range(lens-1, -1, -1):\n",
    "            j = i+1\n",
    "            while j<lens:\n",
    "                if height[j] >= height[i]:\n",
    "                    right[i]+=right[j]\n",
    "                    j+=right[j]\n",
    "                else:\n",
    "                    break\n",
    "        max_rect = 0\n",
    "        for i in range(lens):\n",
    "            max_rect = max(max_rect, height[i] * (left[i]+right[i]-1))\n",
    "        return max_rect\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfLargestArea(self, heights, anotherAreas = None):\n",
    "        length = len(heights)\n",
    "        indexs = [-1] * length\n",
    "        areas = [0] * length\n",
    "        result = 0\n",
    "        for i in range(length):\n",
    "            h = heights[i]\n",
    "            if i == 0:\n",
    "                indexs[i] = -1\n",
    "            elif h > heights[i - 1]:\n",
    "                indexs[i] = i - 1\n",
    "            elif h == heights[i - 1]:\n",
    "                indexs[i] = indexs[i - 1]\n",
    "            else:\n",
    "                index = indexs[i - 1]\n",
    "                while index >= 0 and heights[index] >= h:\n",
    "                    index = indexs[index]\n",
    "                indexs[i] = index\n",
    "            # [indexs[i] + 1， i]的面积\n",
    "            areas[i] = h * (i - indexs[i])\n",
    "            if anotherAreas:\n",
    "                # i这个位置算了两遍，所以减掉h\n",
    "                areas[i] += anotherAreas[length - 1 - i] - h\n",
    "            if areas[i] > result:\n",
    "                result = areas[i]\n",
    "        return result, areas\n",
    "\n",
    "    def largestRectangleArea(self, heights):\n",
    "        \"\"\"\n",
    "        :type heights: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(heights) == 0: return 0\n",
    "        result, area = self.halfLargestArea(heights)\n",
    "        heights.reverse()\n",
    "        result, area = self.halfLargestArea(heights, area)\n",
    "        return result\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def largestRectangleArea(self, heights):\n",
    "        \"\"\"\n",
    "        思路：对于任意一个柱子 i ，找到它左边第一个比它小的数 l，找到它右边第一个比它小的数 r\n",
    "        那么 current max area with h(i) as the height is h(i)*(r-l-1)\n",
    "        然后只要找出这其中最大的一个矩形即可。\n",
    "        找 l 和 r 可以用栈\n",
    "        :type heights: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        left_stack, right_stack = [], []\n",
    "        left_indexes, right_indexes = [-1] * len(heights), [len(heights)] * len(heights)\n",
    "\n",
    "        # left_stack保存的是左边已经遍历过的柱子\n",
    "        # 如果当前的i比left_stack中最后一个元素大，那当前的i就是left_stack中最后一个元素的l\n",
    "        for i in range(len(heights)):\n",
    "            # 这边好像也不能改成if\n",
    "            # 写 if heights[i] < heights[left_stack[-1]]的话，第一个就下标越界了。\n",
    "            while left_stack and heights[i] < heights[left_stack[-1]]:\n",
    "                # 必须用pop，不能用left_stack[-1]\n",
    "                # 因为要保证heights[i]是最小的时候也能跳出循环\n",
    "                right_indexes[left_stack.pop()] = i\n",
    "            # 每一次left_stack的最后一个元素都应该设为当前的i\n",
    "            left_stack.append(i)\n",
    "\n",
    "        # 跟上面的逻辑一样\n",
    "        # 只不过从右往左遍历一次\n",
    "        for i in range(len(heights) - 1, -1, -1):\n",
    "            while right_stack and heights[i] < heights[right_stack[-1]]:\n",
    "                left_indexes[right_stack.pop()] = i\n",
    "            right_stack.append(i)\n",
    "\n",
    "        max_area = 0\n",
    "        for i in range(len(heights)):\n",
    "            area = heights[i] * (right_indexes[i] - left_indexes[i] - 1)\n",
    "            if area > max_area:\n",
    "                max_area = area\n",
    "        print(max_area)\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights):\n",
    "        \"\"\"\n",
    "        :type heights: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not heights:\n",
    "            return 0\n",
    "\n",
    "        stack = [(0, heights[0])]\n",
    "        ans = 0\n",
    "        for i, height in enumerate(heights[1:], 1):\n",
    "            while stack and height < stack[-1][1]:\n",
    "                left = -1 if len(stack) == 1 else stack[-2][0]\n",
    "                ans = max(ans, stack[-1][1] * (i - left - 1))\n",
    "                stack.pop()\n",
    "            stack.append((i, height))\n",
    "\n",
    "        while stack:\n",
    "            left = -1 if len(stack) == 1 else stack[-2][0]\n",
    "            ans = max(ans, stack[-1][1] * (len(heights) - left - 1))\n",
    "            stack.pop()\n",
    "\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "\n",
    "        \n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights):\n",
    "        \"\"\"\n",
    "        :type heights: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        heights.append(-1)\n",
    "        ln=len(heights)\n",
    "        s,res=[[-2,-1]],0\n",
    "        for i,h in enumerate(heights):\n",
    "            if s[-1][0]<=h:\n",
    "                s.append([h,i])\n",
    "            else:\n",
    "                while s[-1][0]>=h:\n",
    "                    x=s.pop()\n",
    "                    res=max(res,x[0]*(i-s[-1][1]-1))\n",
    "                s.append([h,i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfLargestArea(self, heights, anotherAreas = None):\n",
    "        length = len(heights)\n",
    "        indexs = [-1] * length\n",
    "        areas = [0] * length\n",
    "        result = 0\n",
    "        for i in range(length):\n",
    "            h = heights[i]\n",
    "            if i == 0:\n",
    "                indexs[i] = -1\n",
    "            elif h > heights[i - 1]:\n",
    "                indexs[i] = i - 1\n",
    "            elif h == heights[i - 1]:\n",
    "                indexs[i] = indexs[i - 1]\n",
    "            else:\n",
    "                index = indexs[i - 1]\n",
    "                while index >= 0 and heights[index] >= h:\n",
    "                    index = indexs[index]\n",
    "                indexs[i] = index\n",
    "            # [indexs[i] + 1， i]的面积\n",
    "            areas[i] = h * (i - indexs[i])\n",
    "            if anotherAreas:\n",
    "                # i这个位置算了两遍，所以减掉h\n",
    "                areas[i] += anotherAreas[length - 1 - i] - h\n",
    "            if areas[i] > result:\n",
    "                result = areas[i]\n",
    "        print(indexs)\n",
    "        return result, areas\n",
    "\n",
    "    def largestRectangleArea(self, heights):\n",
    "        \"\"\"\n",
    "        :type heights: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(heights) == 0: return 0\n",
    "        result, area = self.halfLargestArea(heights)\n",
    "        print(area)\n",
    "        heights.reverse()\n",
    "        result, area = self.halfLargestArea(heights, area)\n",
    "        print(area)\n",
    "        return result\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = [-1]\n",
    "        heights.append(0)\n",
    "        res = 0\n",
    "        for i in range(len(heights)):\n",
    "            while heights[i]<heights[stack[-1]] :\n",
    "                res = max(res,heights[stack.pop()] * (i-stack[-1]-1))  \n",
    "            stack.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        if n < 1:\n",
    "            return 0\n",
    "        res = self.helper(heights, 0, n-1)\n",
    "        return res\n",
    "\n",
    "    def helper(self, heights, left, right):\n",
    "        if right < left:\n",
    "            return 0\n",
    "        elif right == left:\n",
    "            return heights[left]\n",
    "        mid = left + (right-left)//2\n",
    "        t1 = self.helper(heights, left, mid)\n",
    "        t2 = self.helper(heights, mid+1, right)\n",
    "        t3 = self.helper2(heights, left, mid, right)\n",
    "        return max(t3, max(t1, t2))\n",
    "    \n",
    "    def helper2(self, heights, left, mid, right):\n",
    "        res = 0\n",
    "        i, j = mid, mid+1\n",
    "        min_height = heights[i]\n",
    "        while i >= left and j <= right:\n",
    "            min_height = min(min(heights[i], heights[j]), min_height)\n",
    "            res = max(res, min_height*(j-i+1))\n",
    "            # j += 1; i -= 1\n",
    "            # 对于加减号，一定注意是加号，还是减号\n",
    "            if i == left:\n",
    "                j += 1\n",
    "            elif j == right:\n",
    "                i -= 1\n",
    "            else:\n",
    "                # 此时是两个都没有达到边界的情况\n",
    "                if heights[i-1] > heights[j+1]:\n",
    "                    i -= 1\n",
    "                else:\n",
    "                    j += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        heights.append(-1)\n",
    "        heights_len = len(heights)\n",
    "        sort_stack = collections.deque()\n",
    "        sort_stack.append(-1)\n",
    "        max_area = 0\n",
    "        for i in range(heights_len):\n",
    "            heights_i = heights[i]\n",
    "            queue_right = sort_stack[-1]\n",
    "            while sort_stack and (heights[i] < heights[sort_stack[-1]]) and (sort_stack[-1] != -1):\n",
    "                height_num = heights[sort_stack.pop()]\n",
    "                width = i - sort_stack[-1] - 1\n",
    "                area = width * height_num\n",
    "                max_area = max(area, max_area)\n",
    "            sort_stack.append(i)\n",
    "\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = []\n",
    "        heights = [0] + heights + [0]\n",
    "        res = 0\n",
    "        for i in range(len(heights)):\n",
    "            #print(stack)\n",
    "            while stack and heights[stack[-1]] > heights[i]:\n",
    "                tmp = stack.pop()\n",
    "                res = max(res, (i - stack[-1] - 1) * heights[tmp])\n",
    "            stack.append(i)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        # 维护一个单增的栈，遇到小的数 if stack[top] > new_ele 时\n",
    "        # 用大数的面积更新res\n",
    "        heights = [0]+heights+[0]\n",
    "        stack = []\n",
    "        res = 0\n",
    "        for h_index in range(len(heights)):\n",
    "            while stack and heights[stack[-1]] > heights[h_index]:\n",
    "                cur_height_index = stack.pop()\n",
    "                #print(cur_height_index,len(heights),stack)\n",
    "                res = max(res, heights[cur_height_index]* (h_index-1-stack[-1]) )\n",
    "            stack.append(h_index)\n",
    "        return res\n",
    "\n",
    "        # 1 2 6 4 7 5\n",
    "        # 0\n",
    "        # 0 1\n",
    "        # 0 1 2\n",
    "        # 0 1   3\n",
    "        # 0 1   3 4\n",
    "        # 0 1   3   5\n",
    "\n",
    "        # 1 2 7 6 8 5\n",
    "        # 0\n",
    "        # 0 1\n",
    "        # 0 1 2\n",
    "        # 0 1   3\n",
    "        # 0 1   3 4\n",
    "        # 0 1       5\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        area = 0\n",
    "        stack = collections.deque()\n",
    "        for i, height in enumerate(heights):\n",
    "            while stack and heights[stack[-1]] > heights[i]:\n",
    "                h = heights[stack.pop()]\n",
    "                w = i - stack[-1] - 1 if stack else i\n",
    "                area = max(area, h * w)\n",
    "            stack.append(i)\n",
    "        \n",
    "        while stack:\n",
    "            h = heights[stack.pop()]\n",
    "            w = n - stack[-1] - 1 if stack else n\n",
    "            area = max(area, h * w)\n",
    "\n",
    "        return area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.stack = []\n",
    "\n",
    "    def top(self):\n",
    "        if self.stack == []:\n",
    "            return None\n",
    "        else:\n",
    "            return self.stack[-1]\n",
    "\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        maxArea = 0\n",
    "        for i in range(len(heights)):\n",
    "            topIndex = self.top()\n",
    "            while topIndex!= None and heights[topIndex] > heights[i]:\n",
    "                if len(self.stack) > 1:\n",
    "                    maxArea = max(maxArea, (i-self.stack[-2]-1)*heights[topIndex])\n",
    "                else:\n",
    "                    maxArea = max(maxArea, i*heights[topIndex])\n",
    "                del self.stack[-1]\n",
    "                topIndex = self.top()\n",
    "            self.stack.append(i)\n",
    "        while self.stack != []:\n",
    "            topIndex = self.top()\n",
    "            if len(self.stack) > 1:\n",
    "                maxArea = max(maxArea, (len(heights)-self.stack[-2]-1)*heights[topIndex])\n",
    "            else:\n",
    "                maxArea = max(maxArea, len(heights)*heights[topIndex])\n",
    "            del self.stack[-1]\n",
    "        return maxArea\n",
    "\n",
    "                \n",
    "        \"\"\"\n",
    "        w = [1 for i in range(len(heights))]\n",
    "        for i in range(len(heights)):\n",
    "            j = i\n",
    "            while j > 0 and heights[i] <= heights[j-1]:\n",
    "                w[i] += 1\n",
    "                j -= 1\n",
    "            j = i\n",
    "            while j < len(heights)-1 and heights[i] <= heights[j+1]:\n",
    "                w[i] += 1\n",
    "                j += 1\n",
    "        maxRec = 0\n",
    "        for i in range(len(heights)):\n",
    "            maxRec = max(heights[i]*w[i], maxRec)\n",
    "        return maxRec\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.stack = []\n",
    "\n",
    "    def top(self):\n",
    "        if self.stack == []:\n",
    "            return None\n",
    "        else:\n",
    "            return self.stack[-1]\n",
    "    \n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        maxArea = 0\n",
    "        for i in range(len(heights)):\n",
    "            topIndex = self.top()\n",
    "            while topIndex!= None and heights[topIndex] > heights[i]:\n",
    "                print(i, self.stack)\n",
    "                if len(self.stack) > 1:\n",
    "                    maxArea = max(maxArea, (i-self.stack[-2]-1)*heights[topIndex])\n",
    "                else:\n",
    "                    maxArea = max(maxArea, i*heights[topIndex])\n",
    "                del self.stack[-1]\n",
    "                topIndex = self.top()\n",
    "            self.stack.append(i)\n",
    "            #print(self.stack)\n",
    "        #print(maxArea, self.stack)\n",
    "        while self.stack != []:\n",
    "            topIndex = self.top()\n",
    "            if len(self.stack) > 1:\n",
    "                maxArea = max(maxArea, (len(heights)-self.stack[-2]-1)*heights[topIndex])\n",
    "            else:\n",
    "                maxArea = max(maxArea, len(heights)*heights[topIndex])\n",
    "            del self.stack[-1]\n",
    "        return maxArea\n",
    "\n",
    "                \n",
    "        \"\"\"\n",
    "        w = [1 for i in range(len(heights))]\n",
    "        for i in range(len(heights)):\n",
    "            j = i\n",
    "            while j > 0 and heights[i] <= heights[j-1]:\n",
    "                w[i] += 1\n",
    "                j -= 1\n",
    "            j = i\n",
    "            while j < len(heights)-1 and heights[i] <= heights[j+1]:\n",
    "                w[i] += 1\n",
    "                j += 1\n",
    "        maxRec = 0\n",
    "        for i in range(len(heights)):\n",
    "            maxRec = max(heights[i]*w[i], maxRec)\n",
    "        return maxRec\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from collections import deque\n",
    "    # 可以枚举宽或者枚举高求得总面积\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        if not heights:\n",
    "            return 0\n",
    "        left_height = [0]*len(heights)\n",
    "        left_que = deque()\n",
    "        for i in range(len(heights)):\n",
    "            # 单调栈，从大到小单调递减\n",
    "            while left_que and heights[left_que[-1]]>=heights[i]:\n",
    "                left_que.pop()\n",
    "            left_height[i]= left_que[-1] if left_que else -1\n",
    "            left_que.append(i)\n",
    "\n",
    "        right_height = [0]*len(heights)\n",
    "        right_que = deque()\n",
    "        for i in range(len(heights)-1,-1,-1):\n",
    "            while right_que and heights[right_que[-1]]>=heights[i]:\n",
    "                right_que.pop()\n",
    "            right_height[i]= right_que[-1] if right_que else len(heights)\n",
    "            right_que.append(i)  \n",
    "                 \n",
    "        ans = max((right_height[i]-left_height[i]-1)* heights[i] for i in range(len(heights)))      \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        if not heights:\n",
    "            return 0\n",
    "        max_area = 0\n",
    "        length = len(heights)\n",
    "        begin = [0 for _ in range(length)]\n",
    "        end = [1 for _ in range(length)]\n",
    "        stack = [0]\n",
    "        for i in range(1, length):\n",
    "            cur_height = heights[i]\n",
    "            if not stack or heights[stack[-1]] < cur_height:\n",
    "                begin[i] = i\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                while stack and heights[stack[-1]] > cur_height:\n",
    "                    pre_index = stack.pop()\n",
    "                    end[pre_index] = i\n",
    "                    area = (end[pre_index] - begin[pre_index]) * heights[pre_index]\n",
    "                    max_area = area if area > max_area else max_area\n",
    "                begin[i] = stack[-1]+1 if stack else 0\n",
    "                stack.append(i)\n",
    "        while stack:\n",
    "            pre_index = stack.pop()\n",
    "            end[pre_index] = length\n",
    "            area = (end[pre_index] - begin[pre_index]) * heights[pre_index]\n",
    "            max_area = area if area > max_area else max_area\n",
    "        return max_area\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 单调栈例题\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        # 特殊情况处理\n",
    "        if len(heights) == 0:\n",
    "            return 0\n",
    "        if len(heights) == 1:\n",
    "            return heights[0]\n",
    "        \n",
    "        # 单调栈算法（此题栈结构保持单调递增）\n",
    "        \n",
    "        # 初始化，栈结构头尾加上0作为哨兵位\n",
    "        max_area = 0\n",
    "        stack = [(0, 0)]\n",
    "\n",
    "        # 入栈过程，如果新元素小于栈顶，则弹出栈顶，直到新元素大于栈顶\n",
    "        # 由于最后入栈的哨兵位是0， 所以最终一定会弹出所有非0元素，可以省略出栈过程\n",
    "        for i in range(len(heights)+1):\n",
    "            if i < len(heights):\n",
    "                h = (i+1, heights[i])     # 需要同时记录index\n",
    "            else:\n",
    "                h = (len(heights)+1, 0)\n",
    "\n",
    "            if h[1] >= stack[-1][1]:\n",
    "                stack.append(h)\n",
    "            else:\n",
    "                top_idx, top_num = stack.pop()\n",
    "                # 一边弹出栈顶一边计算构成的矩形面积\n",
    "                while top_num > h[1]:\n",
    "                    length = i - stack[-1][0]      # 长度为当前元素前一位与弹出栈顶元素后新栈顶元素的距离\n",
    "                    area = top_num * length\n",
    "                    if area > max_area:\n",
    "                        max_area = area\n",
    "                    \n",
    "                    # 如果当前元素比栈顶大，则入栈，否则继续循环\n",
    "                    if h[1] >= stack[-1][1]:\n",
    "                        stack.append(h)\n",
    "                        break\n",
    "                    else:\n",
    "                        top_idx, top_num = stack.pop()\n",
    "                    # print(top_num, length, area)\n",
    "\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        lenth = len(heights)\n",
    "        if lenth == 0: return 0\n",
    "        if lenth == 1: return heights[0]\n",
    "        res = 0\n",
    "        stack = [[heights[0], 0]]\n",
    "        left = [-1 for i in range(lenth)]\n",
    "        \n",
    "        for i in range(1, lenth):\n",
    "            while stack and heights[i] <= stack[-1][0]:\n",
    "                stack.pop()\n",
    "            if not stack: left[i] = -1\n",
    "            else: left[i] = stack[-1][1]\n",
    "            stack.append([heights[i], i])\n",
    "        print(left)\n",
    "\n",
    "        stack = [[heights[lenth-1], lenth-1]]\n",
    "        right = [lenth for i in range(lenth)]\n",
    " \n",
    "        for i in range(lenth-2, -1, -1):\n",
    "            while stack and heights[i] <= stack[-1][0]:\n",
    "                stack.pop()\n",
    "            if not stack: right[i] = lenth\n",
    "            else: right[i] = stack[-1][1]\n",
    "            stack.append([heights[i], i])\n",
    "\n",
    "        print(right)\n",
    "        for i in range(lenth):\n",
    "            temp = heights[i]*(right[i]-left[i]-1)\n",
    "            res = max(res, temp)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        l = len(heights)\n",
    "        if l == 0:\n",
    "            return 0\n",
    "        s1 = []\n",
    "        s2 = []\n",
    "        n = []\n",
    "        w = []\n",
    "        for x in range(l):\n",
    "            while s1:\n",
    "                if heights[x] < s1[-1][0]:\n",
    "                    t1 = s1.pop()\n",
    "                    t2 = s2.pop()\n",
    "                    n.append(t1[0])\n",
    "                    w.append(x - t2)\n",
    "                else:\n",
    "                    break\n",
    "            if s1:\n",
    "                if heights[x] == s1[-1][0]:\n",
    "                    s2.append(s2[-1])\n",
    "                else:\n",
    "                    s2.append(s1[-1][1] + 1)\n",
    "            else:\n",
    "                s2.append(0)\n",
    "            s1.append((heights[x], x))\n",
    "        while s1:\n",
    "            t1 = s1.pop()\n",
    "            t2 = s2.pop()\n",
    "            n.append(t1[0])\n",
    "            w.append(l-t2)\n",
    "        print(n, w)\n",
    "        return max([n[x] * w[x] for x in range(l)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        if not heights:\n",
    "            return 0\n",
    "        stack = []\n",
    "        n = len(heights)\n",
    "        lr = []\n",
    "        for _ in range(n):\n",
    "            lr.append([-1,n])\n",
    "        for i in range(n):\n",
    "            while stack and heights[i] < heights[stack[-1]]:\n",
    "                lr[stack[-1]][1] = i               \n",
    "                stack.pop()\n",
    "            if stack :\n",
    "                lr[i][0] = stack[-1]\n",
    "            else:\n",
    "                lr[i][0] = -1\n",
    "            stack.append(i)\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            res.append((lr[i][1]-lr[i][0]-1)*heights[i])\n",
    "        return max(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        l=[]\n",
    "        m=0\n",
    "        helps=[[None,None] for i in range(len(heights))]\n",
    "        for i,h in enumerate(heights):\n",
    "            if len(l)==0 or h>=heights[l[-1]]:\n",
    "                l.append(i)\n",
    "            else:\n",
    "                while len(l)>0 and h<heights[l[-1]]:\n",
    "                    helps[l[-1]][1]=i-1\n",
    "                    l.pop()\n",
    "                l.append(i)\n",
    "        while len(l)>0:\n",
    "            helps[l[-1]][1]=len(heights)-1\n",
    "            l.pop()\n",
    "        for i in range(len(heights)-1,-1,-1):\n",
    "            if len(l)==0 or heights[i]>=heights[l[-1]]:\n",
    "                l.append(i)\n",
    "            else:\n",
    "                while len(l)>0 and heights[i]<heights[l[-1]]:\n",
    "                    helps[l[-1]][0]=i+1\n",
    "                    s=(helps[l[-1]][1]-helps[l[-1]][0]+1)*heights[l[-1]]\n",
    "                    m=m if m>s else s\n",
    "                    l.pop()\n",
    "                l.append(i)\n",
    "        while len(l)>0:\n",
    "            helps[l[-1]][0]=0\n",
    "            s=(helps[l[-1]][1]-helps[l[-1]][0]+1)*heights[l[-1]]\n",
    "            m=m if m>s else s\n",
    "            l.pop()\n",
    "        return m\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        import bisect\n",
    "\n",
    "        left = {}\n",
    "        vals = []\n",
    "        locs = []\n",
    "        maxs = []\n",
    "        for i in range(len(heights)):\n",
    "            if not left:\n",
    "                vals.append(heights[i])\n",
    "                locs.append(i)\n",
    "                maxs.append(i)\n",
    "                left[i] = 0\n",
    "                continue\n",
    "            \n",
    "            x = bisect.bisect_left(vals, heights[i])\n",
    "            vals = vals[:x]\n",
    "            vals.append(heights[i])\n",
    "            locs = locs[:x]\n",
    "            locs.append(i)\n",
    "            maxs = maxs[:x]\n",
    "            if maxs:\n",
    "                left[i] = maxs[-1] + 1\n",
    "            else:\n",
    "                left[i] = 0\n",
    "            maxs.append(i)\n",
    "        \n",
    "        right = {}\n",
    "        vals = []\n",
    "        locs = []\n",
    "        maxs = []\n",
    "        heights_rev = heights[::-1]\n",
    "        for i in range(len(heights_rev)):\n",
    "            if not right:\n",
    "                vals.append(heights_rev[i])\n",
    "                locs.append(i)\n",
    "                maxs.append(i)\n",
    "                right[len(heights) - i - 1] = len(heights) - 1\n",
    "                continue\n",
    "        \n",
    "            x = bisect.bisect_left(vals, heights_rev[i])\n",
    "            vals = vals[:x]\n",
    "            vals.append(heights_rev[i])\n",
    "            locs = locs[:x]\n",
    "            locs.append(i)\n",
    "            maxs = maxs[:x]\n",
    "            if maxs:\n",
    "                right[len(heights) - i - 1] = len(heights) - maxs[-1] - 2\n",
    "            else:\n",
    "                right[len(heights) - i - 1] = len(heights) - 1\n",
    "            maxs.append(i)\n",
    "        \n",
    "        max_area = 0\n",
    "        for i in range(len(heights)):\n",
    "            left_width = i - left[i]\n",
    "            right_width = right[i] - i\n",
    "            area = left_width * heights[i] + heights[i] + right_width * heights[i]\n",
    "            if area > max_area:\n",
    "                max_area = area\n",
    "        \n",
    "        return max_area\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        left, right = [], []\n",
    "        for i in range(len(heights)):\n",
    "            if not left or heights[i] > heights[i-1]:\n",
    "                left.append((0, heights[i]))\n",
    "            else:\n",
    "                j = i-1\n",
    "                while j >= 0 and heights[i] <= heights[j]:\n",
    "                    j -= (left[j][0]+1)\n",
    "                left.append((i-j-1, heights[i]))\n",
    "\n",
    "        for i in range(len(heights)-1,-1,-1):\n",
    "            if not right or heights[i] > heights[i+1]:\n",
    "                right.insert(0, (0, heights[i]))\n",
    "            else:\n",
    "                j = i+1\n",
    "                while j < len(heights) and heights[i] <= heights[j]:\n",
    "                    j += (right[j-i-1][0] + 1)\n",
    "                right.insert(0, (j-i-1, heights[i]))\n",
    "\n",
    "        area = 0\n",
    "        for i in range(len(heights)):\n",
    "            area = max(area, heights[i] * (right[i][0]+left[i][0]+1))\n",
    "        return area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(heights)\n",
    "        r = 0\n",
    "        #print(heights)\n",
    "        while r < n:\n",
    "            if r == 0:\n",
    "                r += 1\n",
    "            while r < n and heights[r] >= heights[r - 1]:\n",
    "                r += 1\n",
    "            i = r - 1\n",
    "            temp = heights[r] if r < n else 0\n",
    "            while i >= 0 and heights[i] > temp:\n",
    "                h = heights[i]\n",
    "                heights[i] = temp\n",
    "                w = r - i\n",
    "                res = max(res, h * w)\n",
    "                i -= 1    \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        heights.append(0)\n",
    "        max_area = heights[0]\n",
    "        for i in range(1,len(heights)):\n",
    "            if heights[i]>=heights[i-1]:\n",
    "                continue\n",
    "            else:\n",
    "                max_area_tmp = 0\n",
    "                j=i-1\n",
    "                while(j>=0 and heights[i]<heights[j]):\n",
    "                    max_area_tmp = max(max_area_tmp,heights[j]*(i-j))\n",
    "                    j-=1\n",
    "                for k in range(j+1,i):\n",
    "                    heights[k] = heights[i]\n",
    "                max_area = max(max_area, max_area_tmp)\n",
    "        return max_area         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        area = 0\n",
    "        heights.append(0)\n",
    "        for pnt in range(len(heights)):\n",
    "            leftbound = 1\n",
    "            while pnt >= 1 and heights[pnt] < heights[pnt-leftbound] and leftbound <= pnt:\n",
    "                area = max(area,heights[pnt-leftbound]*leftbound)\n",
    "                # print(heights[pnt-leftbound]*leftbound)\n",
    "                heights[pnt-leftbound] = heights[pnt]\n",
    "                leftbound += 1\n",
    "        # print(area)\n",
    "        return area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "\n",
    "        if not heights:\n",
    "            return 0\n",
    "\n",
    "        left, right = {}, {}\n",
    "\n",
    "        stack = []\n",
    "        for i in range(len(heights)):\n",
    "            h = heights[i]\n",
    "            while stack:\n",
    "                if heights[stack[-1]] > h:\n",
    "                    right[stack.pop()] = i\n",
    "                else:\n",
    "                    break\n",
    "            stack.append(i)\n",
    "        while stack:\n",
    "            right[stack.pop()] = (i+1)\n",
    "\n",
    "        stack = []  \n",
    "        for i in range(len(heights))[::-1]:\n",
    "            h = heights[i]\n",
    "            while stack:\n",
    "                if heights[stack[-1]] > h:\n",
    "                    left[stack.pop()] = i\n",
    "                else:\n",
    "                    break\n",
    "            stack.append(i)\n",
    "        while stack:\n",
    "            left[stack.pop()] = (i-1)\n",
    "\n",
    "        return max([heights[i]*(right[i]-left[i]-1) for i in range(len(heights))])\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        ret = heights[0]\n",
    "        heights.append(0)\n",
    "        records = []\n",
    "        for i in range(1, len(heights)):\n",
    "            left = i - 1\n",
    "            top = heights[i]\n",
    "            while left >= 0 and heights[left] > top:\n",
    "                temp = heights[left] * (i - left)\n",
    "                if temp > ret:\n",
    "                    ret = temp\n",
    "                heights[left] = top\n",
    "                left -= 1\n",
    "        return ret     \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        self.ans = 0\n",
    "        def calculate(stack, heights):    #根据栈计算面积\n",
    "            for i in range(len(stack)):\n",
    "                area = heights[stack[i]] * (stack[-1] - stack[i] + 1)\n",
    "                if area > self.ans:\n",
    "                    self.ans = area\n",
    "        \n",
    "        stack = []\n",
    "        for i in range(len(heights)):\n",
    "            if stack == []:   #第一个元素\n",
    "                stack.append(i)\n",
    "                calculate(stack, heights)\n",
    "            elif heights[i] > heights[stack[-1]]:   #如果遇到的数大于第一个，那就直接推进去\n",
    "                stack.append(i)\n",
    "                calculate(stack, heights)\n",
    "            elif heights[i] == heights[stack[-1]]:   #相等的时候，计算栈时需要把这个位置给加进去，但是原始的栈不做改动\n",
    "                calculate(stack + [i], heights)\n",
    "            elif heights[i] < heights[stack[-1]]:    #遇到的数小于前一个\n",
    "                while len(stack) >= 2 and heights[i] < heights[stack[-2]]:  #找到比遇到的数大的第一个数\n",
    "                    stack.pop()\n",
    "                for k in range(stack[-1], i):    #从这个数开始把截止到当前数的所有数的值减小\n",
    "                    heights[k] = heights[i]\n",
    "                stack.append(i)\n",
    "                calculate(stack, heights)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        # if len(heights)>=80000:\n",
    "        #     print(len(heights))\n",
    "        #     return 0\n",
    "        # print(len(heights))\n",
    "        # n=7000\n",
    "        # li=[i for i in range(n)]\n",
    "        # heights=li+[n]+li[::-1]\n",
    "    # def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "\n",
    "        # 空间复杂度为常数的算法,不过相应的,由于没有剔除掉连续单调递增的矩形,无法进行跳跃,所以时间消耗会相应地高一些(比如 [1,...,n,n+1,n,...,1]就要n2的复杂度了)\n",
    "        # 从下面的分析可以看出,这种算法并不能确定所有矩形的边界(连续相同的矩形,这可以再次遍历来正确更新所有的边界),但是由于只要求最大值,所以只要确保连续等值矩形的最大边界可以达到就AC了\n",
    "        # 当然,单调栈本身也求不出来精确的双边界\n",
    "        # 矩形左边界的框定是用割除法使前面的所有矩形都是非递减的,这样如果它左边的比它小,不进行计算,如果比它大,削至与其等高,也就扩大了边界\n",
    "        # 至于削除的部分,在削除之前已经达到了左右边界\n",
    "        # 左边界:左边是非递减的,所以即使某些没有达到左边界,也定然有一个达到了真正的左边界,从而获得最大值\n",
    "        # 右边界:我们是遇到右边比这个更小的(出栈)才进行计算的,自然就是右边界\n",
    "        # 右边的框定是每次遇到一个较小的,就把前面比它大的处理掉,由于已经是非递减的了,所以可以直接算面积\n",
    "        # 如果左边碰到的比现在的更小,这意味着目前的这个右边界还未达到,所以不进行计算\n",
    "        # 最后总是以0结尾,这可以保证所以的小的都会计算\n",
    "        heights.append(0)\n",
    "        res = 0\n",
    "        n = len(heights)\n",
    "        for i in range(n - 1):\n",
    "            if heights[i] > heights[i + 1]: # 对应单调栈中的出栈\n",
    "                j = i\n",
    "                while heights[j] > heights[i + 1]: #直到达到入栈条件\n",
    "                    tmp = (i - j + 1) * heights[j]\n",
    "                    if tmp > res:\n",
    "                        res = tmp\n",
    "                    heights[j] = heights[i + 1]# 此处保证前面的是非递减的\n",
    "                    j -= 1 # 削减的部分实际保证的是栈的单调,这与将大的出栈是一样的,也只贡献了heights[i+1]的长度\n",
    "        return res\n",
    "\n",
    "\n",
    "        \n",
    "        # d=[n]*len(heights)\n",
    "        # 单调栈,一次遍历,TC:O(N);SC:O(N)\n",
    "        s=[]\n",
    "        area=0\n",
    "        heights.append(-1)\n",
    "        for i,h in enumerate(heights):\n",
    "            # 连续重复的不用特别处理,也不能特别处理\n",
    "            # if s and s[-1][1]==h:\n",
    "            #     continue\n",
    "            while s and  heights[s[-1]]>h:\n",
    "                    m=heights[s.pop()]\n",
    "                    le=s[-1] if s else -1\n",
    "                    area=max(area,m*(i-le-1))\n",
    "                    # print(j,m,i,le,'area:',m*(i-le-1))\n",
    "            s.append(i) #空间直接减半\n",
    "\n",
    "        # print(s)\n",
    "        return area\n",
    "        # return max(area,len(heights)*s[][1])\n",
    "\n",
    "\n",
    "        for i,h in enumerate(heights):\n",
    "\n",
    "\n",
    "            # 连续重复的不用特别处理,也不能特别处理\n",
    "            # if s and s[-1][1]==h:\n",
    "            #     continue\n",
    "            while s and  s[-1][1]>h:\n",
    "                    j,m=s.pop()\n",
    "                    le=s[-1][0] if s else -1\n",
    "                    area=max(area,m*(i-le-1))\n",
    "                    # print(j,m,i,le,'area:',m*(i-le-1))\n",
    "            s.append((i,h))\n",
    "        # print(s)\n",
    "        return area\n",
    "        # return max(area,len(heights)*s[][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        height_map = []\n",
    "        ans = 0\n",
    "        for i in range(len(heights)):\n",
    "            if not height_map:\n",
    "                height_map.append(i)\n",
    "            # update\n",
    "            else:\n",
    "                for idx in range(len(height_map)-1,-1,-1):\n",
    "                    tmp = height_map[idx]\n",
    "                    if heights[tmp]>=heights[i]:\n",
    "                        height_map.pop()\n",
    "                    else:\n",
    "                        break\n",
    "                height_map.append(i)\n",
    "            # calculate rectangle area \n",
    "            \n",
    "            for idx in range(len(height_map)):\n",
    "                if idx>=1:\n",
    "                    leftID = height_map[idx-1]+1  \n",
    "                else:\n",
    "                    leftID = 0\n",
    "                if ans < (i-leftID+1)*heights[height_map[idx]]:\n",
    "                    ans = (i-leftID+1)*heights[height_map[idx]]\n",
    "                    # print(heights[idx], leftID, i)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        left, right = [], [0] * len(heights)\n",
    "        stack = []\n",
    "        for i, v in enumerate(heights):\n",
    "            while stack and v <= heights[stack[-1]]:\n",
    "                stack.pop()\n",
    "            left.append(stack[-1] if stack else -1)\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i in range(len(heights) - 1, -1, -1):\n",
    "            while stack and heights[i] <= heights[stack[-1]]:\n",
    "                stack.pop()\n",
    "            right[i] = (stack[-1] if stack else len(heights))\n",
    "            stack.append(i)\n",
    "\n",
    "        maxv = 0\n",
    "        for i in range(len(heights)):\n",
    "            maxv = max(heights[i] * (right[i] - left[i] - 1), maxv)\n",
    "        return maxv\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\r\n",
    "        res = 0\r\n",
    "        stack = []\r\n",
    "        for i in range(len(heights)):\r\n",
    "            if len(stack) == 0:\r\n",
    "                stack.append((0, heights[0]))\r\n",
    "            else:\r\n",
    "                index = i\r\n",
    "                while len(stack) != 0 and heights[i] < stack[-1][1]:\r\n",
    "                    index, l = stack.pop()\r\n",
    "                    res = max(res, l*(i-index))\r\n",
    "                if len(stack) == 0 or heights[i] != stack[-1][1]:\r\n",
    "                    stack.append((index, heights[i]))\r\n",
    "        for index, l in stack:\r\n",
    "            res = max(res, l*(len(heights)-index))\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "\n",
    "        lstack = []\n",
    "        rstack = []\n",
    "        lidx = [-1]*len(heights)\n",
    "        ridx = [-1]*len(heights)\n",
    "\n",
    "        for i in range(len(heights)):\n",
    "            while len(lstack) > 0 and heights[lstack[-1]] >= heights[i]:\n",
    "                lstack.pop()\n",
    "            \n",
    "            if len(lstack) == 0:\n",
    "                lidx[i] = -1\n",
    "            else:\n",
    "                lidx[i] = lstack[-1]\n",
    "            \n",
    "            lstack.append(i)\n",
    "\n",
    "        for i in range(len(heights)-1,-1,-1):\n",
    "            while len(rstack) > 0 and heights[rstack[-1]] >= heights[i]:\n",
    "                rstack.pop()\n",
    "            \n",
    "            if len(rstack) == 0:\n",
    "                ridx[i] = -1\n",
    "            else:\n",
    "                ridx[i] = rstack[-1]\n",
    "            \n",
    "            rstack.append(i)\n",
    "\n",
    "        '''\n",
    "        lidx = [-1] * len(heights)\n",
    "        ridx = [-1] * len(heights)\n",
    "\n",
    "        for l in range(1, len(heights)):\n",
    "            if heights[l] > heights[l-1]:\n",
    "                lidx[l] = l-1\n",
    "            elif heights[l] == heights[l-1]:\n",
    "                lidx[l] = lidx[l-1]\n",
    "            else:\n",
    "                i = lidx[l-1]\n",
    "                while i >= 0 and heights[i] > heights[l]:\n",
    "                    i = lidx[i]\n",
    "                \n",
    "                if i < 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    if heights[i] == heights[l]:\n",
    "                        lidx[l] = lidx[i]\n",
    "                    else:\n",
    "                        lidx[l] = i\n",
    "        \n",
    "        for r in range(len(heights)-2,-1,-1):\n",
    "            if heights[r] > heights[r+1]:\n",
    "                ridx[r] = r+1\n",
    "            elif heights[r] == heights[r+1]:\n",
    "                ridx[r] = ridx[r+1]\n",
    "            else:\n",
    "                i = ridx[r+1]\n",
    "                while i >= 0 and heights[r] < heights[i]:\n",
    "                    i = ridx[i]\n",
    "                \n",
    "                if i < 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    if heights[i] == heights[r]:\n",
    "                        ridx[r] = ridx[i]\n",
    "                    else:\n",
    "                        ridx[r] = i\n",
    "        '''\n",
    "        max_area = 0\n",
    "        for i in range(len(heights)):\n",
    "            l = lidx[i]\n",
    "            r = ridx[i]\n",
    "            h = heights[i]\n",
    "            area = h\n",
    "            if l < 0:\n",
    "                area += h*i\n",
    "            else:\n",
    "                area += (i-l-1)*h\n",
    "            \n",
    "            if r < 0:\n",
    "                area += (len(heights)-1-i)*h\n",
    "            else:\n",
    "                area += (r-i-1)*h\n",
    "            \n",
    "            max_area = max(max_area, area)\n",
    "        \n",
    "        return max_area\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        # 单调栈\n",
    "        # 单调栈 从栈底到栈顶 从小到大的下标 每插入一个新的小数值时，都要弹出先前的大数值\n",
    "        # 找每个柱子左右两边第一个小于该柱子的柱子\n",
    "\n",
    "        heights.insert(0, 0)\n",
    "        heights.append(0)\n",
    "        stack = [0]\n",
    "        res = 0\n",
    "\n",
    "        for i in range(1, len(heights)):\n",
    "            # case1 进来的元素大于栈顶的元素\n",
    "            if heights[i] > heights[stack[-1]]:\n",
    "                stack.append(i)\n",
    "            # case2 进来的元素等于栈顶元素\n",
    "            elif heights[i] == heights[stack[-1]]:\n",
    "                stack.pop()\n",
    "                stack.append(i)\n",
    "            # case3 进来的元素小于栈顶元素，抛出所有大于的\n",
    "            # 栈顶：该柱子；即将要入栈：右边第一个矮于当前柱子的；栈顶的下一个元素：左边第一个矮于当前柱子的\n",
    "            else:\n",
    "                while(stack and heights[i] < heights[stack[-1]]):\n",
    "                    midIdx = stack[-1]\n",
    "                    stack.pop()\n",
    "                    if stack:\n",
    "                        left_index = stack[-1]\n",
    "                        width = i - left_index - 1\n",
    "                        height = heights[midIdx]\n",
    "                        res = max(res, width * height)\n",
    "                        print(i, res)\n",
    "\n",
    "                stack.append(i)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        heights.append(0)\n",
    "        len_heights=len(heights)\n",
    "\n",
    "        left=[-1 for i in range(len_heights)]\n",
    "\n",
    "        stack=[]\n",
    "        stack.append(0)\n",
    "        ans=0\n",
    "\n",
    "        for i in range(1,len_heights):\n",
    "            while stack and heights[i]<=heights[stack[-1]]:\n",
    "                ans=max(heights[stack[-1]]*(i-left[stack[-1]]-1),ans)\n",
    "                stack.pop()\n",
    "            left[i]=stack[-1] if stack else -1\n",
    "            stack.append(i)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        # Monotonic Stack\n",
    "        '''\n",
    "        找每个柱子左右侧的第一个高度值小于该柱子的柱子\n",
    "        单调栈：栈顶到栈底：从大到小（每插入一个新的小数值时，都要弹出先前的大数值）\n",
    "        栈顶，栈顶的下一个元素，即将入栈的元素：这三个元素组成了最大面积的高度和宽度\n",
    "        情况一：当前遍历的元素heights[i]大于栈顶元素的情况\n",
    "        情况二：当前遍历的元素heights[i]等于栈顶元素的情况\n",
    "        情况三：当前遍历的元素heights[i]小于栈顶元素的情况\n",
    "        '''\n",
    "\n",
    "        # 输入数组首尾各补上一个0（与42.接雨水不同的是，本题原首尾的两个柱子可以作为核心柱进行最大面积尝试\n",
    "        heights.insert(0, 0)\n",
    "        heights.append(0)\n",
    "        stack = [0]\n",
    "        result = 0\n",
    "        for i in range(1, len(heights)):\n",
    "            # 情况一\n",
    "            if heights[i] > heights[stack[-1]]:\n",
    "                stack.append(i)\n",
    "            # 情况二\n",
    "            elif heights[i] == heights[stack[-1]]:\n",
    "                stack.pop()\n",
    "                stack.append(i)\n",
    "            # 情况三\n",
    "            else:\n",
    "                # 抛出所有较高的柱子\n",
    "                while stack and heights[i] < heights[stack[-1]]:\n",
    "                    # 栈顶就是中间的柱子，主心骨\n",
    "                    mid_index = stack[-1]\n",
    "                    stack.pop()\n",
    "                    if stack:\n",
    "                        left_index = stack[-1]\n",
    "                        right_index = i\n",
    "                        width = right_index - left_index - 1\n",
    "                        height = heights[mid_index]\n",
    "                        result = max(result, width * height)\n",
    "                stack.append(i)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights) -> int:\n",
    "        ans = -inf\n",
    "        stack = []\n",
    "        for i in range(len(heights)):\n",
    "            if not stack or heights[i] >= heights[stack[-1]]:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                while stack and heights[i] < heights[stack[-1]]:\n",
    "                    if len(stack) > 1:\n",
    "                        left = stack[-2] + 1\n",
    "                    else:\n",
    "                        left = 0\n",
    "                    ans = max(ans, heights[stack[-1]] * (i - left))\n",
    "                    stack.pop()\n",
    "                stack.append(i)\n",
    "        while stack:\n",
    "            i = stack.pop()\n",
    "            if len(stack) == 0:\n",
    "                ans = max(ans, heights[i] * len(heights))\n",
    "            else:\n",
    "                ans = max(ans, heights[i] * (len(heights) - 1 - stack[-1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        heights.insert(0, 0)\n",
    "        heights.append(0)\n",
    "        stack = [0]\n",
    "        res = 0\n",
    "        for i in range(len(heights)):\n",
    "            if heights[i] > heights[stack[-1]]:\n",
    "                stack.append(i)\n",
    "            elif heights[i] == heights[stack[-1]]:\n",
    "                stack.pop()\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                while stack and heights[i] < heights[stack[-1]]:\n",
    "                    mid = stack.pop()\n",
    "                    if stack:\n",
    "                        left = stack[-1]\n",
    "                        right = i\n",
    "                        w = right - left - 1\n",
    "                        h = heights[mid]\n",
    "                        res = max(res, h * w)\n",
    "                stack.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        # 引入哨兵\n",
    "        heights = [0] + heights + [0]\n",
    "        stack = []\n",
    "        res = 0\n",
    "\n",
    "        for i in range(len(heights)):\n",
    "            while stack and heights[i] < heights[stack[-1]]:\n",
    "                pop = stack.pop()\n",
    "                w = i - stack[-1] - 1 if stack else i\n",
    "                h = heights[pop]\n",
    "                area = w * h\n",
    "                res = max(res, area)\n",
    "\n",
    "            stack.append(i)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = []\n",
    "        heights.append(0)\n",
    "        heights.insert(0, 0)\n",
    "        res = 0\n",
    "        for i in range(len(heights)):\n",
    "            while stack and heights[i] < heights[stack[-1]]:\n",
    "                top = stack.pop()\n",
    "                res = max(res, heights[top] * (i - stack[-1] - 1))\n",
    "            stack.append(i)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "\n",
    "        height = [0] + heights + [0]  #哨兵,左边保证进栈，右边保证出栈\n",
    "        size = len(height)\n",
    "        max_area = 0\n",
    "        stack = [0]\n",
    "\n",
    "        for i in range(1, size):\n",
    "            while height[i] < height[stack[-1]]:\n",
    "                cur_h = height[stack.pop()]\n",
    "                cur_w = i - stack[-1] - 1\n",
    "                max_area = max(max_area, cur_h*cur_w)\n",
    "            stack.append(i)\n",
    "\n",
    "        return max_area\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(heights)\n",
    "        st = []\n",
    "        l,r = [-1]*n,[n]*n\n",
    "        for i in range(n):\n",
    "            while st and heights[i] < heights[st[-1]]:\n",
    "                j = st.pop()\n",
    "                r[j] = i\n",
    "            st.append(i)\n",
    "        st = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while st and heights[i] < heights[st[-1]]:\n",
    "                j = st.pop()\n",
    "                l[j] = i\n",
    "            st.append(i)\n",
    "        for i in range(n):\n",
    "            ans = max(ans,heights[i]*(r[i]-l[i]-1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        temp = heights[:]\n",
    "        heights = [0]\n",
    "        heights.extend(temp)\n",
    "        heights.append(0)\n",
    "\n",
    "        stk = []\n",
    "        max_area = 0\n",
    "        for i in range(len(heights)):\n",
    "            while len(stk) >= 1 and heights[i] < heights[stk[-1]]:\n",
    "                if len(stk) >= 2:\n",
    "                    max_area = max(max_area, (i - stk[-2] - 1) * heights[stk[-1]])\n",
    "                stk.pop()\n",
    "            stk.append(i)\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        left, right = [0]*n, [0]*n\n",
    "\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while len(stack) != 0 and heights[stack[-1]] >= heights[i]:\n",
    "                stack.pop()\n",
    "\n",
    "            left[i] = stack[-1] if len(stack) != 0 else -1\n",
    "            stack.append(i)\n",
    "            \n",
    "        stack = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while len(stack) != 0 and heights[stack[-1]] >= heights[i]:\n",
    "                stack.pop()\n",
    "            right[i] = stack[-1] if len(stack) != 0 else n\n",
    "            stack.append(i)\n",
    "        \n",
    "        print(left)\n",
    "        print(right)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, (right[i] - left[i]-1)*heights[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        heights=heights+[0]\n",
    "        lenh=len(heights)\n",
    "        stack=[-1]\n",
    "        res=[]\n",
    "        for i,height in enumerate(heights):\n",
    "            while height<heights[stack[-1]]:\n",
    "                temp=stack.pop()\n",
    "                res.append(heights[temp]*(i-stack[-1]-1))\n",
    "            stack.append(i)\n",
    "        return 0 if res==[] else max(res)\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        temp = [heights[i] for i in range(len(heights))]\n",
    "        heights = [0]\n",
    "        heights.extend(temp)\n",
    "        heights.append(0)\n",
    "\n",
    "        max_area = 0\n",
    "        # 单调栈\n",
    "        stk = []\n",
    "        for i in range(len(heights)):\n",
    "            while len(stk) >= 1 and heights[i] < heights[stk[-1]]:\n",
    "                if len(stk) >= 2:\n",
    "                    max_area = max(max_area, (i - stk[-2] - 1) * heights[stk[-1]])\n",
    "                    # print(max_area, stk)\n",
    "                stk.pop()\n",
    "            stk.append(i)\n",
    "        return max_area\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack=[]\n",
    "        res=[0]*len(heights)\n",
    "        for idx in range(len(heights)):\n",
    "            while stack and heights[idx]<heights[stack[-1]]:\n",
    "                mid=stack.pop()\n",
    "                if stack:\n",
    "                    left=stack[-1]\n",
    "                else:\n",
    "                    left=-1\n",
    "                right=idx\n",
    "                res[mid]=heights[mid]*(right-left-1)\n",
    "            stack.append(idx)\n",
    "        while stack:\n",
    "            mid=stack.pop()\n",
    "            right=len(heights)\n",
    "            if stack:\n",
    "                left=stack[-1]\n",
    "            else:\n",
    "                left=-1           \n",
    "            res[mid]=heights[mid]*(right-left-1)\n",
    "        print(res)\n",
    "        return max(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        # 单调栈 双单调栈找左/右小值\n",
    "        h = [0] + heights + [0]\n",
    "        n = len(h) \n",
    "        stack = []\n",
    "        rmi = [0] * n\n",
    "        for i, v in enumerate(h):  # L->R 单调递减栈\n",
    "            while stack and h[stack[-1]] > v:\n",
    "                rmi[stack.pop()] = i\n",
    "            stack.append(i)\n",
    "        #print(rmi, stack, [h[i] for i in rmi])\n",
    "        stack = []\n",
    "        lmi = [0] * n\n",
    "        for i in range(n-1, -1, -1):  # R->L 单调递减栈\n",
    "            while stack and h[stack[-1]] > h[i]:\n",
    "                lmi[stack.pop()] = i\n",
    "            stack.append(i)\n",
    "        #print(lmi, stack, [h[i] for i in lmi])\n",
    "        #print([(rmi[i]-lmi[i]-1)*h[i] for i in range(n)])\n",
    "        return max((rmi[i]-lmi[i]-1)*h[i] for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        left, right = [0]*n, [0]*n\n",
    "        satck = []\n",
    "        for i, val in enumerate(heights):\n",
    "            while satck and heights[satck[-1]] >= val:\n",
    "                satck.pop()\n",
    "            left[i] = satck[-1] if satck else -1\n",
    "            satck.append(i)\n",
    "        \n",
    "        satck = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while satck and heights[satck[-1]] >= heights[i]:\n",
    "                satck.pop()\n",
    "            right[i] = satck[-1] if satck else n\n",
    "            satck.append(i)\n",
    "        \n",
    "        return max([(right[i]-left[i]-1)*heights[i] for i in range(n)])\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        # 记录当前柱子，左边第一个比自己低以及右边第一个比自己低的柱子的下标\n",
    "        left_next_min, right_next_min = [-1 for _ in range(n)], [n for _ in range(n)]\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and heights[i] < heights[stack[-1]]:\n",
    "                i_top = stack.pop()\n",
    "                # 栈里面的柱子确定右边第一个比自己低的柱子下标\n",
    "                right_next_min[i_top] = i\n",
    "            if stack:\n",
    "                # 很巧妙的办法，当前柱子左边第一个比自己低柱子下标\n",
    "                left_next_min[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        # 以当前柱子为高能组成的面积列表，每一根柱子都计算，最大面积则是列表中的最大值\n",
    "        areas = [heights[i] * (right_next_min[i] - left_next_min[i] - 1) for i in range(n)]\n",
    "        return max(areas)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        left_smaller = [-1] * n\n",
    "        right_smaller = [n] * n\n",
    "        s_left = []\n",
    "        s_right = []\n",
    "        for i in range(n):\n",
    "            while s_right and heights[s_right[-1]] > heights[i]:\n",
    "                right_smaller[s_right.pop()] = i\n",
    "            s_right.append(i)\n",
    "            while s_left and heights[s_left[-1]] > heights[n - i - 1]:\n",
    "                left_smaller[s_left.pop()] = n - i - 1\n",
    "            s_left.append(n - i - 1)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res = max(res, (right_smaller[i] - left_smaller[i] - 1) * heights[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        next_lower = [-1] * len(heights)\n",
    "        stacks = []\n",
    "        stacks_idx = []\n",
    "        for i in range(len(heights)):\n",
    "            stacks.append(heights[i])\n",
    "            stacks_idx.append(i)\n",
    "            while len(stacks) > 1 and stacks[-1] < stacks[-2]:\n",
    "                next_lower[stacks_idx[-2]] = i - 1\n",
    "                stacks[-2] = stacks[-1]\n",
    "                stacks.pop()\n",
    "                stacks_idx[-2] = stacks_idx[-1]\n",
    "                stacks_idx.pop()\n",
    "        for i in stacks_idx:\n",
    "            next_lower[i] = len(heights) - 1\n",
    "        \n",
    "        stacks = []\n",
    "        stacks_idx = []\n",
    "        prev_lower = [-1] * len(heights)\n",
    "        for i in range(len(heights)-1, -1, -1):\n",
    "            stacks.append(heights[i])\n",
    "            stacks_idx.append(i)\n",
    "            while len(stacks) > 1 and stacks[-1] < stacks[-2]:\n",
    "                prev_lower[stacks_idx[-2]] = i + 1\n",
    "                stacks[-2] = stacks[-1]\n",
    "                stacks.pop()\n",
    "                stacks_idx[-2] = stacks_idx[-1]\n",
    "                stacks_idx.pop()\n",
    "        for i in stacks_idx:\n",
    "            prev_lower[i] = 0\n",
    "        \n",
    "        # print(next_lower)\n",
    "        # print(prev_lower)\n",
    "        ans = 0\n",
    "        for i in range(len(heights)):\n",
    "            ans = max(ans, (next_lower[i] - prev_lower[i] + 1) * heights[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        heights = [0] + heights + [0]\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        for i, height in enumerate(heights):\n",
    "            if not stack:\n",
    "                stack.append((i, height))\n",
    "                continue\n",
    "            if stack and height >= stack[-1][-1]:\n",
    "                stack.append((i, height))\n",
    "            elif stack and height < stack[-1][-1]:\n",
    "                while stack and height < stack[-1][-1]:\n",
    "                    cur_i, cur_height = stack.pop()\n",
    "                    ans = max(ans, (i-stack[-1][0]-1)*cur_height)\n",
    "                stack.append((i, height))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack=[(-2,-1)]\n",
    "        ans=0\n",
    "        heights=heights+[0]\n",
    "        for i,j in enumerate(heights):\n",
    "            while len(stack)>1 and heights[stack[-1][1]]>j:\n",
    "                ans=max(ans,heights[stack[-1][1]]*(i-stack[-1][0]-1))\n",
    "                stack.pop(-1)\n",
    "            stack.append((stack[-1][1],i))\n",
    "\n",
    "        return ans "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
